백준/9461 파도반 수열 / 다이나믹프로그래밍 + 제출전 최악의경우 체크해보기

파도반 수열 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

76537

33556

27488

42.495%

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스마다 P(N)을 출력한다.

예제 입력 1 복사

2
6
12

예제 출력 1 복사

3
16

---

풀이

/*
어떤 규칙이 있나 살펴보면 f(n) = f(n-1) + f(n-5)의 규칙을 알 수 있다.
예를들어 7이 어떻게 구해졌나 보면 바로 뒤숫자인 5와 , 5번째전인 2와 합쳐져서 생성된다.
규칙을 찾았으니 규칙을 가지고 메모이제이션을 진행해서 풀이해보자.
 */

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    /*
    어떤 규칙이 있나 살펴보면 f(n) = f(n-1) + f(n-5)의 규칙을 알 수 있다.
    예를들어 7이 어떻게 구해졌나 보면 바로 뒤숫자인 5와 , 5번째전인 2와 합쳐져서 생성된다.
    규칙을 찾았으니 규칙을 가지고 메모이제이션을 진행해서 풀이해보자.
     */

    static int testcase;
    static int n;
    static long[] memoization = new long[101];

    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        testcase = Integer.parseInt(br.readLine());
        //기저 상태 넣어놓기
        memoization[1] = 1;
        memoization[2] = 1;
        memoization[3] = 1;
        memoization[4] = 2;
        memoization[5] = 2;
        memoization[6] = 3;
    }

    static void solve() throws IOException {
        for (int i = 0; i < testcase; i++) {
            n = Integer.parseInt(br.readLine());
            bottomUp(n);
            bw.write(memoization[n]+"\n");
        }
    }

    static void bottomUp(int n) {
        for (int i = 7; i <=n; i++) {
            if (memoization[i] == 0) { // 다른 테스트케이스 덕분에 이미 채워져있을수도 있으니까.
                memoization[i] = memoization[i - 1] + memoization[i - 5];
            }
        }
    }
}

 

중요한점

최악의경우인 n이 1일때와 100일때를 넣어보지않았다면

n이 100일때 int형 숫자범위를 넘는다는것을 몰랐을것이다!

제출전 꼭 체크하자.