백준 17137번 문제(사탕 놀이) 파이썬(Python) 풀이 [로밍맨]

문제 링크

https://www.acmicpc.net/problem/17137

17137번: 사탕 놀이

 

정답 코드는 아래와 같습니다.

DIV = 1000000007
 
def solve():
  n = int(input())
  arr = [int(x) for x in input().split()]
  arr.sort()
  cache = list(range(arr[-1]*n, 0, -n))
  for i in range(n-2, -1, -1):
    for j in range(arr[i] - 2, -1, -1):
      cache[j] = (cache[j] + cache[j+1]) % DIV
  print(cache[0])
 
t = int(input())
for _ in range(t):
  solve()
 

 

정답 코드는 20줄도 채 안되지만 이 문제는 상당히 어려운 문제입니다.

 

일단 지문을 읽고 어떻게 풀어야 할지 막막하다면 정상입니다.

어떻게 풀어야 할지 모르겠을 때에는 주어진 예제를 직접 시도하면서 스스로의 직관이 무언가 발견하기를 바라야 합니다.

나열을 해보면 규칙성과 중복된 연산을 찾을 수 있습니다.

아래 풀이 영상을 보기 전에 직접 시도하면서 저처럼 규칙성과 중복된 연산을 찾아보시기 바랍니다.

 

728x90

 

좀 쉬운 문제라면 이런 규칙성과 중복된 연산을 찾기만 해도 그 다음에는 어떻게 해야할 지 보일텐데, 이 문제는 그렇지 않습니다. 그 이유는 2차원 DP 이기 떄문입니다.

DP 문제는 식을 세우면 바로 풀리기 때문에 식을 세우려고 시도하는 경우가 많은데요. 2차원 DP의 경우 식을 세우는 것이 쉽지 않습니다.

따라서 식을 먼저 세우기 위해 시도하는 것보다 2차원 형태에서 어디의 값을 채울 수 있는지 보고 채울 수 있는 값들을 채워나가다보면 어떤식으로 채워나가면 좋을지 그 방향이 보일 수 있습니다.

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=SWb2OZGs2w0 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)