[백준] 단계별로 풀어보기(단계:15,동적계획법1,JAVA)9461번, 파도반 수열

문제 링크

9461번: 파도반 수열

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적계획법이란 위 문제와 같이 동일한 연산을 계속 반복하여 비효율적으로 코드가 실행되어 그것을 향상시키기 위하여반복되는 연산의 결과를 따로 저장하여 적재적소에 코드가 더 효율적으로 만드는 방법입니다.

아래 표는 N의 따른 파도판 수열에 값입니다.

N	파도판 수열의 수
1	1
2	1
3	1
4	2
5	2
6	3
7	4
8	5
9	7
10	9
11	12

표에서 파도판의 수를 보면 규칙을 찾을 수 있습니다.

N을 개수를 뜻하는 단어로 생각하고 규칙을 쓰면

N = (N-2) + (N-3)입니다.

예를 들어 n=10일 때 n=8일때와 n=7일때를 더하면  N = 4 + 5으로 9입니다.

N의 최대값으로 100을 기준으로 메모이제이션 배열 크기를 101로 설정하였습니다.

 

• 함수 값 저장할 메모이제이션 배열 check를 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• 파도판 수열의 값을 구하는 함수 wave을 만들었습니다.
• 함수의 결과를 BufferedWriter에 저장하여 결과를 출력하였습니다.

• check가 null이 아니면 메모이제이션에 저장된 값이 있기에 그 값을 가져온다.
• null인 경우 재귀를 반복하여 결과값을 메모이제이션에 저장한 뒤 반환한다.
• 위에 알고리즘 설명을 토대로 wave 함수를 작성하였습니다.

결과 코드

import java.io.*;
public class Main{
	static long[] check = new long[101];	//메모이제이션배열
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //BufferedWriter를 통해 결과 값 출력
        //-------입력값 저장 및 함수 실행---------
    	int index = Integer.parseInt(br.readLine());
    	checkInit();
    	for(int i=0;i<index;i++) {
    		int num = Integer.parseInt(br.readLine());
        	bw.write(wave(num) + "\n");	//함수 결과 BufferedWriter에 저장
    	}
    	bw.flush();	//결과 출력
    	bw.close();
    	br.close();
	}
    //-------------파도반 수열 함수-----------
	public static long wave(int n) {
		if(check[n]!=0)		//메모이제이션 값 존재시 그 값 반환
			return check[n];
		check[n]=wave(n-2) + wave(n-3);	//재귀 진행
		return check[n];
	}
    //---------------배열 초기화----------------
	public static void checkInit() {
		check[1] = 1;	//N=1일 때 1
		check[2] = 1;	//N=2일 때 1
		check[3] = 1;	//N=3일 때 1
	}
}