[백준, Java] 4811번, 알약(DP, 재귀)

문제 링크

4811번: 알약

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. N개의 알약이 담긴 병이 존재합니다.

2. 하루의 1번 반 조각의 약을 먹으며, 꺼낸 약이 반 조각이 아니면 반으로 쪼개서 먹고 남은 조각은 병에 다시 넣는다.

3. 한 조각을 꺼낸 날은 W, 반 조각을 꺼낸 날은 H을 손녀에게 메시지를 보냅니다.

4. 2N일이 지나면 2N길이의 메시지 문자열이 만들어질 때 서로 다른 문자열의 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 약의 개수가 1 ~ N(30)까지의 서로 다른 문자열의 개수를 탐색합니다.

 

3. 입력되는 알약의 개수에 따라 탐색했던 서로 다른 문자열의 개수를 결과로 출력합니다.

 

서로 다른 문자열 개수 탐색(DP)

약을 꺼내는 과정의 경우를 살펴보면 위 그림처럼 점점 경우의 수가 퍼져나가는 것을 확인할 수 있습니다.

 

 

또한, 해당 탐색을 반복하게 되면 중복되는 탐색이 발생합니다.

 

▶︎ 해당 중복되는 탐색을 메모이제이션하여 중복된 탐색을 방지하도록 합니다.

 

 

메모이제이션을 하는 배열 : DP[h][w]

 

h :  한 조각 약의 개수

 

w : 반 조각 약의 개수

 

DP[h][w] : 병의 한 조각 h개와 반 조각 w개가 있을 때 서로 다른 문자열의 개수

 

만약, 병의 3개의 약이 있다고 존재하면 DP[3][0]의 값을 결과로 출력하면 됩니다.

 

⭐️ 반 조각의 알약은 한 조각의 알약을 1번 이상써야 존재하는 값인 것을 기억하셔야 합니다.

 

종수가 선택할 수 있는 경우의 수는 2가지입니다.

 

한 조각의 알약이 1개 이상 존재할 때

 

h : h -1(한 조각의 알약 반으로 나누었기 떄문에 1개가 감소)

 

w : w + 1(한 조각의 알약을 반으로 나누어서 반 조각의 알약이 1개가 생성)

 

반 조각의 알약이 1개 이상 존재할 때

 

h : h (반 조각만 사용하기 때문에 감소하지 않음)

 

w : w - 1(반 조각만 사용하기 때문에 1개 감소)

 

 

즉, 위 경우의 수를 기반으로 재귀를 통해 메모이제이션을 진행하여 탐색을 진행합니다.

 

※ 예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

n = { 6, 1, 4, 2, 3, 30 }

 

 

2. 약의 개수가 1 ~ N(30)까지의 서로 다른 문자열의 개수를 탐색합니다.

 

DP[1][0] = 1

DP[2][0] = 2

DP[3][0] = 5

....

 

 

3. 입력되는 알약의 개수에 따라 탐색했던 서로 다른 문자열의 개수를 결과로 출력합니다.

 

n = 6 :132

n = 1 :1

n = 4 :14

n = 2 :2

n = 3 :5

n = 30 : 3814986502092304

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• search함수를 약의 개수가 1 ~ 30일 때 서로 다른 문자열의 개수를 탐색합니다.
• 탐색으로 얻은 값을 기준으로 n이 주어질 때 서로 다른 문자열의 개수를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 재귀와 메모이제이션 및 경우의 수를 통해서 DP[][]에 약에 따른 서로 다른 문자열의 개수를 탐색합니다.

결과코드

import java.io.*;
import java.util.*;

public class Main {
  //메모이제이션을 진행할 DP 배열
  static long[][] DP = new long[31][31];
  public static void main(String[] args) throws IOException {
    //입력값 처리하는 BufferedReader
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    //결과값 출력하는 BufferedWriter
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    //DP[0][0]은 문자열 완성의 값으로 1으로 초기화
    DP[0][0] = 1;
    // 1 ~ 30까지 서로 다른 문자열 개수 탐색
    search(30, 0);
    //입력되는 n에 따른 서로 다른 문자열 개수 조회 및 출력
    while(true){
      int n= Integer.parseInt(br.readLine());
      if(n== 0){
        break;
      }
      //DP[n][0]으로 메모이제이션을 진행한 정보 조회 후 BufferedWriter 저장
      bw.write(String.valueOf(DP[n][0]));
      bw.newLine();
    }
    bw.flush();		//결과 출력
    bw.close();
    br.close();
  }
  //알약 경우의 수를 통해 탐색 진행
  static long search(int h, int w){
    //문자열이 완성되었을 때
    if(DP[h][w] != 0){
      return DP[h][w];
    }
    long hVal = 0;
    long wVal = 0;
    //한 조각의 약을 꺼낸 경우
    if(h > 0){
      hVal = search(h -1 , w+1);
    }
    //반 조각의 약을 꺼낸 경우
    if(w > 0){
      wVal = search(h, w-1);
    }
    //메모이제이션 진행
    DP[h][w] = hVal + wVal;
    return DP[h][w];
  }
}