[다이나믹 프로그래밍] 9461번 - 파도반 수열

[백준] 9461번 - 파도반 수열

(한줄평) 손으로 직접 쓰면서 규칙을 알아냈던 문제! 하나씩 다 해보다보면 규칙이 보기도한다는 것을 꺠닫게 되었다!

풀이 시간: 20분 이내

1) 문제 해결 아이디어

첫 정삼각형의 변의 길이는 1이고 나선 모양으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 떄, 그 변에 길이가 k인 정삼각형을 추가한다. 이러한 행위를 반복 했을 때 나선에 있는 정삼각형의 변의 길이 p(n)을 구하는 문제다. 이 문제는 직접 하나하나 써보면서 규칙을 찾을 수 있는 문제였다.

Q. dp테이블을 전연변수로 선언하고 입력을 받기전에 100까지 계산을 하는 이유는?

사실 n을 입력받고 나서 p(n)값을 계산해도 상관 없지만 테스트 케이스가 2이상일 경우에 기록된 값에 대해 또 계산을 하게 된다. 예를들어 n이 10, 20이 들어왔다고 하면 p(10)을 계산할 떄 d[6] ~d[10]까지 기록하는데 p(20)을 계산할 떄 위에서 기록했던 값을 또 계산해서 기록하게 된다. 굳이 중복으로 계산할 필요가 없기 때문에 dp테이블을 전역변수로 선언하고 d[100]까지 모든 값을 기록해 놓는 것이다.

 

<점화식>

 

2) 소스코드

t = int(input())  # 테스트 케이스 수
d = [0] * 101
d[1:6] = [1, 1, 1, 2, 2]  # 1~5번째 값 초기화
for i in range(6, 101):
  d[i] = d[i - 1] + d[i - 5]

for _ in range(t):
  n = int(input())  # 1이상 100이하
  print(d[n])