알고리즘
백준 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();
}
}