오늘은 별찍는 문제를 풀어보려 한다. 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 위가 포문
음..근데 생각해보니 백준 서버에 따라 차이가 있을것 같다..ㅋㅋ
'공부 > 알고리즘' 카테고리의 다른 글
| [Java 코딩테스트] 백준 10818 문제풀이 / 배열 없이 최소 최대 구하기 (0) | 2021.07.22 |
|---|---|
| [Java 코딩테스트] 백준 1110 문제풀이 / 더하기 사이클 (0) | 2021.07.22 |
| [Java 코딩테스트] 백준 15552번 문제 풀이 (0) | 2021.07.18 |
| [Java 코딩테스트] 백준 2884번 문제풀이 (0) | 2021.07.18 |
| [Java 코딩테스트] 백준 2753번 문제풀이 (0) | 2021.07.13 |
