[백준][JAVA] 9461 - 파도반 수열 - DP

📌 문제

백준 | 파도반 수열 | SILVER 3 | DP

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

 

📌 문제 탐색하기

• 정삼각형이 나선(오른쪽 시계방향)으로 계속 돌면서 모양을 만듬

 

 

📌 알고리즘

• P(N)이 구현되는 모습이, 그 전의 값들로부터 영향을 받아 구현되기 때문에 이 문제는 ‘DP’ 알고리즘으로 풀 수 있다.
• 이를 구현하기 위해, Memoization 을 활용한다.

example) P(N) = 1, 1, 1, 2, 2, 3, 4, 5, 7, 9

N	0	1	2	3	4	5	6	7	8
P(N)	0	1	1	1	2	2	3	4	5
							P[1] + P[5]	P[2] + P[6]	P[3] + P[7]

즉, P(N) = P(N-5) + P(N-1) (단, N>=5)

 

 

📌 코드 설계하기

1. TEST 입력
2. MEMOIZATION 기법을 활용해 101(즉, 100까지) 크기의 배열에 모든 수열의 값 입력
3. 이후, TEST CASE에따른 답변 출력

 

 

📌 시도 회차 수정 사항

1회차

• 배열을 int로 하니, 틀린 문제로 인식됐다.
• int의 최대 범위는 약 21억인데, 피보나치와 같이 n이 커질수록 결과값도 같이 증가하는 수식에서는 int를 초과할 경우가 많으므로 long을 사용하는 것이 좋다.

### 틀린 코드 ###
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class q9461_silver3 {
    public static void main(String[] args) throws IOException {
        int[] p = new int[101];
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        p[1] = p[2] = p[3] = 1;
        p[4] = p[5] = 2;

        int t = Integer.parseInt(br.readLine());

        for (int i = 6; i < 101; i++) {
            p[i] = p[i - 5] + p[i - 1];
        }

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(p[n]);
        }
    }
}

📌 2회차 정답 코드

• 이를 long으로 변경했더니 옳은 답변 완성 !!
• 그리고, 타 풀이에서 i-2, i-3으로 점화식을 잡았던데… 나선형 모습에서 보면 i-5, i-1이 옳은 풀이라 생각한다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int answer = 0;

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] dp = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<n; i++){
            int num = Integer.parseInt(st.nextToken());
            arr[i] = num;
        }

        for(int i = 0; i<n; i++){
            dp[i] = arr[i];
            for(int j = 0; j<i; j++){
                if(arr[i] > arr[j]){
                    dp[i] = Math.max(dp[i], dp[j] + arr[i]);
                }
            }
            answer = Math.max(answer, dp[i]);
        }

        System.out.println(answer);
    }
}

 

 

이번 문제는 비교적 DP 문제들 중에서도, '피보나치 수열'과 비슷한 문제라 금방 풀 수 있었다.

다만, 코딩테스트에서는 히든케이스에 따른 시간초과를 알 수 없으니.. 문제 정리할 때 항상 int, long 등 선택을 신중히 해야겠다.