Baekjoon(백준) 25090번 - d1000000 (Google Codejam 2022 qualification problem C)

백준 25090번.
문제 제목 : d1000000
백준 25090

2022 구글 코드잼의 qualification round 에서 C 번 문제로 나왔다. (A, B 번은 너무 쉬워서 패스)

문제 해석

어떤 주사위에 k 개의 면이 있다면 그 주사위는 1 ~ k의 자연수를 나타낼 수 있다. N 개의 주사위에 대해 각각 몇 개의 면이 있는지 주어지고 이 때 이 주사위들로 만들 수 있는 연속적으로 증가하는 자연수 수열의 최대 길이가 얼마인지 계산하는 것이다.

풀이 전략

아이디어는 간단하다. 일단 각 주사위는 1 ~ k의 자연수를 나타낼 수 있으므로 최대 길이가 되도록 연속 증가 수열을 만들려면 그 수열은 1부터 시작하는 것이 가장 최적의 방법이다. (어차피 모든 주사위가 1에서 부터 표현 가능한 숫자가 시작되므로)
또한, k 가 큰 주사위는 더 큰 숫자들도 나타낼 수 있으므로 아껴야 한다. 따라서, 작은 자연수는 k 가 작은 주사위로 최대한 나타내야 한다. 즉, 1부터 자연수를 1씩 증가시키면서 k가 작은 주사위부터 사용해가며 각 수를 나타낼 수 있는지 보면 된다. 만약 나타내고 싶은 자연수가 남아 있는 주사위 중 k가 가장 작은 주사위로 커버가 안된다면 그 수를 나타낼 수 있으면서 k가 최소인 주사위를 이용해야 한다. 그런 식으로 하면 최대 길이가 얼마인지 계산할 수 있다. 즉, greedy 기법이다.

구현

앞에서 설명한 것과 같이 구현하면 된다. k가 작은 주사위부터 사용하려면 입력으로 받은 각 주사위 면의 개수를 오름차순으로 정렬하고 저 알고리즘을 적용하면 된다.
자세한 solution 코드는 github에 있다.

baekjoon 25090 solution code