알고리즘

백준 14606 피자 (Small)

킨글 2024. 8. 30. 20:50

설명

1 2 3 4 5 6 7 8 9 10
0 1 3 6 10 15 21 28 36 45

사이사이 숫자 값들이 1, 2, 3, 4 이런식으로 늘어난다.

- 1에서 2는 1 

- 2에서 3은 2

- 3에서 4는 3 ...

이것을 코드로 풀어보면 dp[i] = dp[i-1] - dp[i-2] + 1 + dp[i-1]이다. 

즉, 뒤에숫자 - 앞에숫자 + 1 + 원래숫자이다. 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    // 14606
    public static void main(String[] args) throws IOException {
        process();
    }

    private static void process() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N+1];
        dp[1] = 0;
        if(N == 1) {
            bw.write(dp[1] + "");
            bw.flush();
            bw.close();
            br.close();
            return;
        }
        dp[2] = 1;

        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i-1] - dp[i-2] + 1 + dp[i-1];
        }
        bw.write(dp[N] + "");

        bw.flush();
        bw.close();
        br.close();
    }
}