약 - 백준 BOJ 23560

https://www.acmicpc.net/problem/23560

23560번: 약

 

 

---

접근법

나는 아직 ps 내공이 부족해서 그런지 문제를 딱 보고 이런 유형이겠다 싶은게 떠오르지가 않는다

늘 그렇듯 브루트 포스, 완전탐색 수행 이후 해당 풀이에서 최적화를 진행하는 식으로 문제를 접근했다

 

배열 arr 를 자연수 1 ~ N 까지 오름차순으로 채운 뒤, 약을 구분하기 위해서

 

원소를 2로 나눈 나머지를 통해 아침, 점심, 저녁 약을 구분했다

완전 탐색을 수행할 경우, 투포인터 재귀를 통해 각 단계에서 현재 먹어야 할 양의 종류와 각  양 끝의 약 종류 비교를 통해 탐색을 수행하게 했다

 

// 식사 enum
enum Medicine {
    BREAKFAST,
    LUNCH,
    DINNER
}

// ...

static int dfs(int[] arr, int left, int right, Medicine currMedicineToConsume) {
    if(left > right) {
        return 1;
    }

    Medicine nextMedicine = getMedicineFromElement(currMedicineToConsume.ordinal() + 1);

    if(currMedicineToConsume.equals(Medicine.LUNCH)) {
        return getMedicineFromElement(arr[left]).equals(currMedicineToConsume)
                ? dfs(arr, left + 1, right, nextMedicine)
                : dfs(arr, left, right - 1, nextMedicine);
    }

    int sum = 0;

    // 아침 저녁은 같은 케이스로 처리. 점심약만 아니면 됨
    if(getMedicineFromElement(arr[left]).equals(Medicine.LUNCH) == false) {
        sum += dfs(arr, left + 1, right, nextMedicine);
    }
    if(getMedicineFromElement(arr[right]).equals(Medicine.LUNCH) == false) {
        sum += dfs(arr, left, right - 1, nextMedicine);
    }
    return sum;
}

static Medicine getMedicineFromElement(int element) {
    return Medicine.values()[element % 3];
}

 

 

답은 잘 나온다. 헌데 N 이 최대 15라서 시간복잡도가 O( 2^N ) 로 시간초과가 발생한다

재귀함수를 통해 공간해를 탐색하는 모양을 그려보면 피보나치 수를 구하는 것과 비슷한 모양이 나온다, 즉 DP 로 접근하는 문제임을 알 수 있다

 

 

---

풀이

DP 인건 알겠다

근데 점화식이 잘 떠오르지가 않는다,,,

30분이 지나도 풀이가 안떠올라 다른사람 풀이를 봤는데, 다들 쉽다고 하길래 ps 를 더 열심히 해야겠다 자극을 받았다,,, :)

 

 

N 이 2일때의 경우의 수를 살펴보자

 

 

 

위 사진처럼, N = 2 일 때 6 가지의 경우의 수가 나온다

 

{ 아침, 점심, 저녁 } 세끼를 한 사이클로 봤을 때, 아침 -> 아침의 변화를 보면 다음과 같은 그림이 나오는데

 

 

 

점심은 어떻게 먹든 한가지 경우의 수만 나오는걸 고려할 때,

 

• 연속되게 붙어있는 아침,점심,저녁 약을 먹었을때 ( { 3, 4, 5, }, { 0, 1, 2 } )
• 양 사이드에서 아침과 저녁을 다르게 떼어먹었을 때 ( { 2, 3, 4 }, { 1, 2, 3 } )

 

그 다음 경우의 가짓수가 달라지는 것을 볼 수 있다 ( 전자는 다음에 두가지로 경우의 수가 갈라지고, 후자는 오직 한개만 )

 

따라서 하루치의 약을 먹는 경우의 수를 메모이제이션 할 때

 

연속된 약을 먹는 경우와, 양 사이드에서 약을 떼어먹는 경우, 이렇게 두가지의 경우에 대해

연속된 약을 먹는 경우는 이전값의 두배를, 양 사이드에서 떼어먹은 경우는 이전값을 그대로 가져온 값을,

최종적으로 두 값을 더한 값을 현재 값에 업데이트 해주면서 문제를 해결할 수 있다

 

 

---

코드

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

enum MealTime {
    BREAKFAST,
    LUNCH,
    DINNER
}

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] dp = new int[n];

        dp[0] = 2;

        for(int i = 1; i < n; i++) {
            dp[i] = dp[i - 1] * 2 + dp[i - 1];
        }

        System.out.println(dp[n - 1]);
    }
}