2023.12.17.

Softeer 문제 풀이 - 3문제

 

1. H-클린알파 - Lv.4

간단한 수학 문제, 그냥 각 시간마다 현재까지 존재하는 바이러스 증식, 이후에 바이러스 유입된 만큼 증가 시키면 됨.

어제 풀었던 Lv.4랑 많이 난이도가 차이났음. 이건 백준에서는 브론즈 정도의 문제 아닌가 싶을 정도로 쉬움.

다만 좀 주의해야할 점은 32-bit integer가 아니라 64-bit 자료형을 사용해야 오버플로우 문제가 안 날듯?

(나는 걍 어지간하면 long long으로 선언하고 사용해서 별 문제 없었음.)

 

2. [HSAT 6회 정기 코딩 인증평가 기출] 출퇴근길 - Lv.3

좀 생각을 해야 풀 수 있는 그래프 문제.

S -> E, E -> S 두 경로에 대해서 모두 속할 수 있는 노드들의 개수를 구하는 건데, 이를 만족하는 노드 K는 S- > K, K -> S, E -> K, K -> E 모두 가능하니 각 간선별로 역으로 이어준 간선도 생성, 원래 간선 기준으로 S, E에서 시작했을 때 도달할 수 있는 노드들 구하고, 역 간선 기준으로 또 S,E를 시작점으로 BFS를 돌렸을 때 도달할 수 있는 노드들(이러면 K->S, K->E가 되는지도 구할 수 있음.)을 구한다.

그런데, 원래 간선에서는 각각 E, S에 도착하면 더 이상 움직이지 못하니 그걸 따로 처리해준다. (역 간선에서 이를 막으면 S에서 시작했을 때에 S를 재방문 하는 것도 막게 되는 거라서 역 간선에서 BFS 돌렸을 때는 이렇게 처리해주면 안 됨.)

이게 처음에 푼 Lv.4보다 훨씬 어려운 것 같은데 왜 Lv.3인지 모르겠다. 정답률도 꽤나 낮던데...

 

3. 바이러스 - Lv.2

1번 문제보다는 조금 더 쉬운문제.

((P^N)*K)%1'000'000'007을 출력하면 되는 문제인데, N의 범위가 작아 O(N)으로도 풀 수 있고 당연히 O(logN)으로도 가능함.

그런데 파이썬으로 했을 때는 왜 틀린지 모르겠음. 

이게 Lv.2면 1번 문제도 Lv.2가 적당할듯?

 

[모두의 랜덤 디펜스] - 실랜디 

 

시험시간 : 120분, 실제 : 48분만에 올솔

Solved : 4/4

 

4. BOJ 1380 귀걸이 - S5

그냥 각 학생들마다 기록에서 몇 번씩 불렸는지를 배열 등으로 저장하고, 그 중에서 한 번만 기록에서 나온 학생을 출력하는 문제.

BOJ 27111번이 생각나는 문제인데, 이 문제가 좀 더 쉬운 것 같다.

그런데 학생들의 이름에 공백이 존재할 수 있어서 C++로 '\n' 기준으로 전체를 한 번에 받아야 하므로, 그냥 파이썬으로 풀었다.

'A', 'B'는 왜 있는지 잘 모르겠음. (기여할려고 들어가니 다들 같은 생각을 하는 듯.)

 

5. BOJ 16508 전공책 - S3

비트마스킹 + 브루트포스 문제로 N이 작아 2^N가지의 경우의 수를 다 확인할 수 있음.

각 문자열마다의 알파벳 분포를 벡터에 저장하여 관리, 경우의 수마다 포함되는 문자열들의 알파벳 분포를 합치고 합친 결과가 원하는 단어의 알파벳 분포를 전부 넘기면 답을 갱신하면 풀림.

 

6. BOJ 4097 수익 - S2

구간 합 문제로 며칠 전에 다시 풀어본 BOJ 1912랑 같은 문제.

Kadane Algorithm이라는 알고리즘으로 풀린다고 하는데, 나는 그냥 p[i...j] 가 j가 마지막 원소로 존재하는 구간 합 중 최댓값이라면 p[1..i-1]는 p[1...k] (k<j) 중에서 최솟값이어야 한다는 성질로 풀었음.

(max(p[1..j] - p[1..k])를 원하고 p[1...j]가 고정이라면 p[1...k]가 최소여야 하니깐 이렇게 풀 수 있음.)

 

7. BOJ 25194 결전의 금요일 - S1

좀 고전했던 문제.

일단 문제에서 원하는 것은 임의의 원소들을 몇 개를 선택했을 때, 선택한 원소들의 합이 7로 나누었을 때 나머지가 4인 경우가 존재하는지의 여부인 것을 어렵지 않게 파악은 했다.

그런데 이후에 이걸 또 어떻게 구하지 싶었는데, 생각해보니 각 원소들을 7로 나눈 나머지가 가치인 동전들로 생각하면 동전 DP로 풀 수 있었다.

S1이 아니라 G5가 맞지않나 싶은데, 이게 5중 포문으로 브루트포싱해서 풀린다길래 신기했음.

 

오늘 일지는 여기서 끝.