백준 9461번
https://www.acmicpc.net/problem/9461
그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.
파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.
N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.
재귀함수를 사용해서 문제를 쉽게 풀 수 있었다.
삼각형의 가장 큰 변을 찾는 규칙은 간단하다.
N번째 위치의 삼각형의 변의 길이를 찾는다고 했을 때,
N-3번째 위치 + N-2번째 위치의 삼각형 변의 길이합이 N번째 변의 길이 값이된다.
static long DP(long depth) {
// 가장 긴변을 찾아야 함
// 만들려는 가장 긴 변은 memoization[depth-3] + memoization[depth-2]의 값이다.
for(int i=4; i<=depth; i++) {
if(memoization[i] == 0) {
memoization[i]= DP(i - 3) + DP(i - 2);
}
}
return memoization[(int) depth];
} // End of DP
재귀 구조는 그냥 반복되는 규칙되로 depth
의 값 까지 반복하며
DP의 함수값을 memoization
배열에 저장해 나가면 된다.
import java.io.*; public class Main { static long memoization[] = new long[101]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); memoization[1] = 1; memoization[2] = 1; memoization[3] = 1; int T = Integer.parseInt(br.readLine()); while(T-->0) { int N = Integer.parseInt(br.readLine()); sb.append(DP(N)).append('\n'); } System.out.println(sb); } // End of main static long DP(long depth) { // 가장 긴변을 찾아야 함 // 만들려는 가장 긴 변은 memoization[depth-3] + memoization[depth-2]의 값이다. for(int i=4; i<=depth; i++) { if(memoization[i] == 0) { memoization[i]= DP(i - 3) + DP(i - 2); } } return memoization[(int) depth]; } // End of DP } // End of Main class