백준 9461. 파도반 수열(JAVA)

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

public class Main {
	
	static Long[] dp = new Long[101];
	
	public static void main(String[] arge) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int test_case = Integer.parseInt(br.readLine());
		
		dp[1] = 1L;
		dp[2] = 1L;
		dp[3] = 1L; 
		dp[4] = 2L;
		dp[5] = 2L;

		while(test_case --> 0) {
			int N = Integer.parseInt(br.readLine());
			sb.append(p(N)).append("\n");
		}
		System.out.println(sb);
	}
	static long p(int num) {
		
		if(dp[num] == null) {
			dp[num] = p(num - 1) + p(num - 5);
		}	
		return dp[num];
	}
}

○ 문제 요약 

 

첫 정삼각형 변의 길이는 1이다. 변의 길이를 가지고 만들 수 있는 가장 큰 삼각형을 만들어서 입력받은 N번째에 해당하는 삼각형 변의 길이를 출력해라.

 

○ 문제 풀이

 

이전에 포스팅한 동적 계획법을 적용하면 쉽게(?) 풀 수 있었다.

N의 범위가 1 ~ 100이므로 값을 저장하기 위해 배열의 길이를 101로 dp를 선언했다.(int 타입으로 선언하면 int가 표현할 수 있는 범위를 넘어가기 때문에 Long 타입으로 선언했다.) N의 범위 1 ~ 5는 초기화를 통해 먼저 값을 정해주었다. 

 

dp[6]을 구하는 과정

N의 범위가 6이상일 때, 구하는 공식을 보면 다음과 같다.

p(N) 공식

 N이 6일 경우를 예로 설명을 하자면 p(6)을 실행하면 dp[6]은 현재 값이 없으므로 if문을 충족한다.

그래서 if문 안에 공식 dp[6] = p(5) + p(1)이 성립한다. 재귀 호출을 통해 dp[5] = 2 이므로 2를 넘겨주고 dp[1] = 1이므로 마찬가지로 1을 넘겨준다. dp[6] = 2 + 1이 되어 3이라는 값을 반환해주고 p(6)의 값을 출력할 수 있다.

 

어려운 문제는 아니었지만 결과를 보면 시간 초과와 메모리 초과 때문에 해결하느라 시간을 더 소요했다.

그래도 동적 계획법 알고리즘을 어떻게 사용하는 건지 감을 좀 잡은 거 같아서 나름 의미있는 문제 풀이였다.

밑에 코드 블럭은 처음 시간 초과를 받은 코드인데 이 글을 보시는 분들에게 반면교사가 될 수 있었으면 하는 마음에 같이 첨부했다.

 

○ 결과

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static Integer[] dp = new Integer[101];
	
	public static void main(String[] arge) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int test_case = Integer.parseInt(br.readLine());
		
		dp[1] = 1;
		dp[2] = 1;
		dp[3] = 1; 
		dp[4] = 2;
		dp[5] = 2;

		for(int i = 0 ; i < test_case ; i++) {
			int N = Integer.parseInt(br.readLine());
			System.out.println(p(N));
		}	
	}
	static Integer p(int num) {
		if(num == 1 || num == 2|| num == 3 ) {
			 dp[num] = 1;
		}
		if(num == 4 || num == 5) {
			dp[num] = 2;
		}
		if(num > 5 && num <= 100) {
			dp[num] = p(num - 1) + p(num - 5);
		}	
		return dp[num];
	}
}