알고리즘

[백준] 9461 파도반 수열 - 실버 3

swanzzz 2025. 5. 31. 22:40
반응형

[오늘의 문제]

 

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

[오늘의 학습 키워드]

  • DP
  • 구현

1. 문제설명

 

삼각형이 위 그림과 같은 모양으로 계속 추가되는 수열의 형태를 띄고 있습니다.

 

주어진 그림에서 삼각형의 가장 긴 변의 길이를 구하려고 하는데 그 변에 길이가 k일때 그 변에 길이가 k인 정삼각형을 추가합니다.

 

이런식으로 N회 반복을 수행할 때 N번째 삼각형의 변의 길이를 구하는 프로그램을 만드는 문제 입니다.

[제한사항]

  • 시간 제한 1초
  • 메모리 제한 128MB
  • 1 ≤ N ≤ 100

2. 접근방식

 

이번 문제는 굉장히 쉽게 해결할 수 있습니다.

 

주어진 문제에서 P(1) 부터 P(10) 까지의 변의 길이가 주어집니다.

 

그 길이는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 라고 합니다.

 

그럼 역순으로 9를 만드려면 4 + 5 가 되어야 합니다.

 

7을 만들기 위해서는 3 + 4가 되어야 겠죠

 

이런식으로 규칙을 찾아보면 DP[i] 번째 값을 만들기 위해서는 i - 2 와 i - 3 의 값을 각각 더해주어야 합니다.

 

이를 코드로 구현해 보았습니다.

3. 코드

import sys
input = sys.stdin.readline

# 테스트 케이스
T = int(input())
for _ in range(T):

    # 입력
    N = int(input())
    # DP 테이블 초기화
    DP = [1] * (N + 1)

    # 점화식 토대로 값 구하기
    for i in range(4, N + 1):
        DP[i] = DP[i - 2] + DP[i - 3]
    
    print(DP[N])

 

[코드설명]

처음 테스트 케이스가 주어지고 구하려는 변의 순서가 주어집니다.

 

이를 토대로 DP 테이블을 초기화 해 나가면 되죠

 

앞서 그림에서 P(1), P(2),  P(3) 의 길이가 모두 1 이었습니다.

 

따라서 DP 테이블을 처음 초기화 할때 1로 모두 초기화 하고 점화식을 토대로 값을 찾아줍니다.

 

값이 변화하는 시점은 4번째 부터 값이 변화하기 시작합니다. 

 

따라서 반복문의 시작 지점을 4부터 N + 1 까지로 설정해 주는데 만약 N이 4 미만이 주어진다면

 

반복문의 범위가 제대로 설정되지 않기 때문에 건너뛰고 바로 결과를 출력해 주겠죠

 

4 이상이 주어진 경우 설정한 점화식을 토대로 값의 반복을 시작합니다.

 

현재 DP[i] 번째 값을 찾기 위해서 설정한 점화식이 DP[i - 2] + DP[i - 3] 이기 때문에 이렇게 반복을 실시해 주고 결과를 출력해 주었습니다.

4. 결과

[회고]

 

이번 문제는 굉장히 쉬웠습니다.

 

이제까지 조금 어려운 수준의 DP 문제들을 해결하다 보니 수를 나열했을때 자연스럽게 규칙이 눈에 보였고

 

손으로 적어서 규칙의 검증을 거쳤습니다.

 

그 결과 바로 점화식을 찾을 수 있었고 그를 토대로 문제를 해결할 수 있었습니다.

 

아직은 DP 문제 해결에 자신이 없지만 계속 풀어보며 실력을 키우겠습니다.

 

반응형