[백준] 단계별로 풀어보기(단계:15,동적계획법1,JAVA)1932번, 정수 삼각형

문제 링크

1932번: 정수 삼각형

 

www.acmicpc.net

---

주의사항

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

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

---

문제 설명

---

접근 방법

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

아래 표는 예제 1에 표현한 것입니다.

				7
			3		8
		8		1		0
	2		7		4		4
4		5		2		6		5

규칙과 표에 선택된 것을 살펴보면 규칙이 보인다.

5

7

38

810

2744

45265

배열로 보면 자신아래 같은 행에 다음열과 다음열을 선택하도록 하는 경우의 수가 있습니다.

예를 들어 [0][0]=7이면 선택되는 것은[1][0]=3이랑 [1][1]=8으로 더해서 합해진다.

삼각형에 크기의 배열로 [index][index]으로 메모이제이션을 구성하였습니다.

 

• 함수 값 저장할 메모이제이션 배열 check를 만들었습니다.
• 삼각형 숫자를 저장하는 num을 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• 삼각형 값에 최대값을 얻는 함수 triangle을 만들었습니다.

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

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static Integer[][] check;	//메모이제이션 배열
	static Integer[][] num;		//숫자 저장 배열
	static int index;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기

        //------------------입력값 저장 및 배열 초기화-------------
    	index = Integer.parseInt(br.readLine());
    	num = new Integer[index][index];
    	check = new Integer[index][index];
    	StringTokenizer st;
    	for(int i=0;i<index;i++) {
    		st= new StringTokenizer(br.readLine());
    		for(int j=i;j>=0;j--) {
    			num[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	System.out.println(triangle(0, 0) + "\n");	//결과 출력
    	br.close();
	}
    //-----------정수 삼각형 함수 최대값 함수----------------
	public static Integer triangle(int depth,int current) {
		if(depth==index-1)	//삼각형 수 다 더했을 때
			return num[depth][current];
            
		if(check[depth][current]!=null)	//메모이제이션 값 존재시
			return check[depth][current];
		//재귀
		check[depth][current] = Math.max(triangle(depth+1, current), 
        triangle(depth+1, current+1)) + num[depth][current];
		
		return check[depth][current];	//결과 반환
		}
	}