Baekjoon 문제 17211번 좋은 날 싫은 날

문제 출처:https://www.acmicpc.net/problem/17211

17211번: 좋은 날 싫은 날

Baekjoon 17211번 문제 좋은 날 싫은 날

---

문제 분석

이 문제를 풀기 위해서 먼가 재귀적으로 접근해야 할 것 같다는 느낌이 들었습니다.

좋은 날을 0으로 싫은 날을 1로 두고 예제를 살펴보면,

• 00[좋은날 -> 좋은날] 0.70
• 01[좋은날 -> 싫은날] 0.30
• 10[싫은날 -> 좋은날] 0.50
• 11[싫은날 -> 싫은날] 0.50

처음에 1[싫은날]로 시작하여 각각 좋은 날과 싫은 날의 확률을 구해야합니다. 

• 좋은날[110 + 100] : 0.50 X 0.50 + 0.50 X 0.70 = 0.60
• 싫은날[111 + 101] : 0.50 X 0.50 + 0.50 X 0.30 = 0.40

그럼 N이 3이 주어진다고 한다면 어떻게 될까요?

 

• 좋은날[1100 + 1000 + 1110 + 1010] : 0.50 X 0.50 X 0.70 + 0.50 X 0.70 X 0.70 + 0.50 X 0.50 X 0.50 + 0.50 X 0.30 X 0.50 = 0.62
• 싫은날[1101 + 1001 + 1111 + 1011] : 0.50 X 0.50 X 0.30 + 0.50 X 0.70 X 0.30 + 0.50 X 0.50 X 0.50 + 0.50 X 0.30 X 0.50 = 0.38

흠.. 규칙을 잘 모르겠다고요? 그럼 접은 글을 참고해주세요

if N == 2

• 좋은날[110 + 100] : 0.50 X 0.50 + 0.50 X 0.70 = 0.60
• 싫은날[111 + 101] : 0.50 X 0.50 + 0.50 X 0.30 = 0.40

 if N == 3

• 좋은날[1100 + 1000 + 1110 + 1010] : 0.50 X 0.50 X 0.70 + 0.50 X 0.70 X 0.70 + 0.50 X 0.50 X 0.50 + 0.50 X 0.30 X 0.50 = 0.62
• 싫은날[1101 + 1001 + 1111 + 1011] : 0.50 X 0.50 X 0.30 + 0.50 X 0.70 X 0.30 + 0.50 X 0.50 X 0.50 + 0.50 X 0.30 X 0.50 = 0.38

 

네 보시는 바와 같이 중복적인 N-1의 값과 현재 값의 곱으로 이루어졌습니다. 

이러한 규칙을 잘 이용하면 재귀적으로 충분히 구현할 수 있습니다.

N을 1씩 감소시키면서 N이 0인 이점을 base case로, 그 이외의 부분은 recursive case로 구현하면 됩니다.

---

코드는 다음과 같습니다:

#include <iostream>
#define GOOD 0
#define BAD 1

using namespace std ; 

double rate[2][2] ;
double good[2][101] ;
double bad[2][101] ;

double days_later_good(short days, bool curr_day_type){
    if(days == 0){
        if(!curr_day_type)
            return 1.0 ;
        else
            return 0.0 ;
    }
    double & temp = good[curr_day_type][days] ;
    if(temp != -1.0) return temp ;
    return temp = rate[curr_day_type][GOOD] * days_later_good(days-1, GOOD) + rate[curr_day_type][BAD] * days_later_good(days-1, BAD);
}

double days_later_bad(short days, bool curr_day_type){
    if(days == 0){
        if(curr_day_type)
            return 1.0 ;
        else
            return 0.0 ;
    }
    double & temp = bad[curr_day_type][days] ;
    if(temp != -1.0) return temp ;
    return temp = rate[curr_day_type][GOOD] * days_later_bad(days-1, GOOD) + rate[curr_day_type][BAD] * days_later_bad(days-1, BAD);
}

int main(){
    short N ;
    bool is_bad_day ;
    cin >> N >> is_bad_day ;
    for (int i = 0; i < 2; i++){
        cin >> rate[i][GOOD] >> rate[i][BAD] ;
        for (int j = 0; j < 101; j++){
            good[i][j] = -1;
            bad[i][j] = -1;
        }
    }
    cout << int(days_later_good(N, is_bad_day) * 1000) << endl << int(days_later_bad(N, is_bad_day) * 1000) << endl ;
    return 0 ; 
}

해당 문제는 Github에서도 보실 수 있습니다:

https://github.com/gurcks8989/CodingTest/blob/master/BackJoon/HPS/P17211_Good%26Bad_Day.cpp

GitHub - gurcks8989/CodingTest: CodingTest_study_with_c++

훈수 및 조언은 언제든 환영입니다.