[Java 코딩테스트] 백준 2438 문제풀이 Dynamic Programming

2438번 문제

오늘은 별찍는 문제를 풀어보려 한다. 2438번 문제 같은 경우에는 for문을 중첩하여 풀 수 있고, 어렵지 않으니 코드를 바로 공유하겠다.

import java.util.Scanner;

public class Number2438 {
	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		for(int i = 0; i < T; i++) {
			for(int j = 0; j <= i; j++)
				System.out.print("*");
			System.out.println();
		}
	}
}

그런데 우리는 해당 문제를 풀기 위해 Dynamic Programming을 이용할 수도 있다. 동적 계획법이라고도 하는데, DP로 흔히 부른다.

DP를 쉽게 설명하자면, "앞선 문제를 풀어놓고 다음 문제를 푸는 것"이라고 할 수 있겠다. 감이 잘 안올텐데, DP와 관련된 글을 따로 작성하여 본 게시글에 첨부할 테니, 더 궁금하다면 해당 글을 봐 달라.

---

그러면 어떻게 DP를 별 찍기에 이용할 수 있느냐? 문제의 출력을 보면, 별이 하나씩 순차적으로 늘어나는 것을 볼 수 있다.

즉, "앞선 레벨의 별은 이미 찍혀있고, 뒤 레벨에는 앞의 별에 하나를 추가해주면 된다." 라는 발상을 할 수 있다. 

주어진 T 크기의 배열을 만들고, 앞에서부터 별을 채워나가면 된다. 또한 재귀 호출 형식으로 만들 예정이고, base는 다음과 같다.

base case: index == 배열의 길이 Then 배열 반환
recursive case: 배열[index-1] + "*"

또한 별은 앞 레벨부터 찍을 것이기 때문에, 최초의 index는 0이 된다. 이 때, 배열[0-1] 은 존재하지 않기 때문에 따로 index가 0인 경우에 대하여 array[0] = "*"을 해준다.

따라서 전체 코드는 다음과 같다.

import java.util.Scanner;

public class Number2438DP {
	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		String[] star = new String[T];
//		createStar(star, 0);
//		for(int i = 0; i < star.length; i++) {
//			System.out.println(star[i]);
//		}
		setStar(star);
        
        for(int i = 0; i < star.length; i++){
			System.out.println(star[i]);
		}
	}
	
	static void setStar(String[] arr){
		for(int i = 1; i < arr.length; i++)
			arr[i] = arr[i-1] + "*";
	}
    
	static String[] createStar(String[] arr, int index) {
		if(index == arr.length)
			return arr;
		
		if(index == 0)
			arr[index] = "*";
		else
			arr[index] = arr[index-1] + "*";
		
		return createStar(arr, index+1);
	}
}

보면 String[] star= new String[T];를 통해 주어진 크기만큼 별의 문제를 풀 String 배열을 선언하고, 해당 배열의 0번 index부터 별을 채워나간다.

arr[index] = arr[index-1] + "*";

해당 줄을 보면, 현재 index의 배열은 index-1의 배열에 *을 더해준다.

결과는 정답!

---

궁금해서 포문으로 돌렸을 때랑 비교해 봤다.

아래가 DP 위가 포문

음..근데 생각해보니 백준 서버에 따라 차이가 있을것 같다..ㅋㅋ