2024.04.08. ~ 2024.04.14.

백준 6 문제.

 

1. BOJ 22251 : 빌런 호석 - G5

Implementation + Bruteforcing 문제.

 

두 숫자간에 7개의 표시등 중에서 몇 개나 차이가 나는지를 미리 계산을 해둔다.

이후에 1 ~ N까지 숫자에 대해서 X와 표시등의 차이가 1개 이상 P개 이하인 숫자들을 모두 찾아보면 된다.

표시등 개수의 차이는 각각 자리 별로 비교를 해보면 되니, 총 시간복잡도는 O(NK)가 된다.

 

2. BOJ 16876 : 재미있는 숫자 게임 - G2

Game Theory + DP 문제.

 

M번째 턴이 끝난 순간에 결과가 0~N이라면 cubelover, N+1 ~ 9999 이면 koosaga가 이긴게 된다.

 

그렇다면 M번째 턴이 짝수면 cubelover, 홀수면 koosaga의 턴일텐데, cubelover의 턴일 경우에는 M-1번째 턴이 끝난 순간의 결과들 중 0 ~ N으로 만들 수 있는 수면 해당 수는 cubelover가 확정적으로 이기고,아니면 koosaga가 이기는 수가 된다.

 

역으로, koosaga의 턴일 때에는 M-1번째 턴이 끝나는 순간의 결과들 중 N+1 ~ 9999로 만들 수 있는 수면 koosaga가 이기는 수가 된다. 못 만든다면 cubelover가 이긴다.

 

이렇게 역순으로 M번째 턴이 끝나는 순간부터 처음 시작하는 수까지 O(40000 * M) DP를 돌려보면 처음 수가 N인 경우 누가 이기는지를 파악할 수 있다. 총 시간복잡도는 O(40000 * M)이다. Game Theory DP를 많이 안 풀어본 입장으로써 입문하기 좋은 문제라 생각한다.

 

3. BOJ 10610 : 30 - S4

Greedy + Sorting + Math 문제.

 

30의 배수가 되는 조건은 10의 배수가 되면서 3의 배수가 되면 된다.

그렇다면 10의 배수가 되는 조건은 맨 끝자리 수가 0이면 되므로 (0, 10, ... 등등.) 0이 있는지의 여부로 판별하면 된다.

3의 배수는 모든 자리 수를 합쳤을 때 3의 배수라는 특징을 가지고 있다.

 

그래서 모든 자리수들을 보았을 때 0이 존재하며 각 자리 수의 합이 3의 배수임을 확인하면 30의 배수가 되는 수를 만들 수 있음을 알 수 있는데, 그 중에서 제일 큰 수는 사실상 각 자리 수를 내림차순으로 정렬한 결과가 된다. (내림차순으로 정렬하면 제일 마지막 수는 0이 오므로 10의 배수가 되며, 3의 배수는 모든 자릿수의 합과 관련이 있어서 정렬 순서와는 관련이 없다.) 

 

참관 알바하러 가면서 폰으로 풀었는데, 꽤 괜찮았던 문제.

 

4. BOJ 15663 : N과 M (9) - S2

Backtracking 문제.

 

구현이 약간 귀찮은데, 나는 중복되는 순열을 set으로 전부 처리해서 풀었다.

이외에는 그냥 Backtracking + 배열로 중복 방문을 하지 않도록 처리해서 풀면 된다.

 

5. BOJ 17836 : 공주님을 구해라! - G5

Math + BFS 문제.

 

공주와 전설의 검까지 가는 최단거리는 BFS를 통해서 각각 구할 수 있고, 전설의 검을 얻으면 공주까지 맨허튼 거리만큼 빨리 갈 수 있다. 그래서 BFS를 한 후에 검을 얻고 가는게 이득인지 아닌지를 판별하면 된다.

 

예전에 엄청 많이 틀렸었던 문제. 바로 풀어서 감회가 새로웠다.

 

6. BOJ 23632 : 쿠키런 킹덤 - G1

Topological Sorting + Implementation 문제.

 

현재 지어진 건물들 중 한 건물이라도 a라는 자원을 생산할 수 있다면 a 자원은 0초만에 무한히 생성이 가능하니 a만 있으면 건설이 가능한 건물들은 모두 지을 수 있다. 이를 활용해서 indegree를 재료 개수로 생각하면서, 각 건물을 건설할 때 처음으로 특정 자원을 생산할 수 있다면 이와 관련된 건물들의 indegree를 하나씩 차감하면서 Topological Sorting을 돌리면 된다.

 

Topological Sorting 아이디어는 어렵지 않게 나왔으나 구현에서 약간 애먹은 문제.

 

이번 주 일지는 여기서 끝.