[BAEKJOON] 2156 포도주 시식

일단 이 문제를 보고 처음 든 생각은 바로 한칸을 뛰거나 아니면 두칸을 뛰고 대신 3개를 연속으로 뛰지 않는 문제를 생각했다.

그래서 첫번째 코드를 짰다.

첫번째 실패

#include <iostream> #include <fstream> #include <vector> #include <algorithm> using namespace std; int cup_count, drinking_amount; vector<int>alchol; void drinking_wine(int index, int before_flag, int result) { if (index >= cup_count) { drinking_amount = max(result, drinking_amount); return; } if (before_flag < 2) //만약 이전에 한칸 뛰었으면 { drinking_wine(index + 1, before_flag + 1, alchol[index + 1] + result); //한 칸 뛰기 drinking_wine(index + 2, 1, alchol[index + 2] + result); //두 칸뛰기 } //연속으로 한칸 한칸 뛰었으면 else drinking_wine(index + 2, 1, alchol[index + 2] + result); //두 칸뛰기 } int main() { ifstream fcin; fcin.open("2156_input.txt"); fcin >> cup_count; alchol = vector<int>(20000, 0); for (int j = 0; j < cup_count; j++) fcin >> alchol[j]; drinking_amount = 0; drinking_wine(0, 1, alchol[0]); drinking_wine(1, 1, alchol[1]); cout << drinking_amount << endl; system("pause"); }

dp를 사용하지 않았고 단지 한칸을 뛰거나 두칸을 뛰고 만약 그 범위가 일정 범위가 넘어서면

결과값을 저장하는 형식으로 짰다 즉 아래부터 더해서 올라오는 것이다.

이것은 모든 결과값을 계산해야한다. 따라서 시간초과가 나왔다..

위를 수정하여 2번째 코드를 만들었다. 먼저 dp인데 memorization을 사용하지 않아서 시간초과가 뜬 것이므로 배열을 만들었다.

처음에는 1차 배열을 만들었는데 전혀 도움이 되지 않았다.

그러다 다른 문제가 생각났다. 스티커라는 문제였던 것 같은데 1번째 뛰는 것과 2번째 뛰는 것의 저장 부분을 나눈 것이다.

따라서 아래와 같이 코드를 만들었다.

한칸 뛸때와 두칸 뛸때의 경우를 나누어 저장하였고, 한칸 아니면 두칸을 뛰도록 만들었다.

하지만 이 코드는 틀렸습니다. 왜 틀렸을까..생각을 해보았다. 하지만 생각나지 않았다..

두번째 실패

#include <iostream> #include <fstream> #include <vector> #include <algorithm> using namespace std; int cup_count; vector<int>alchol; vector<vector<int>> cache; int drinking_wine(int index, int before_flag, int flag) { if (index >= cup_count) return alchol[index]; int&ret = cache[flag][index]; if (ret != 0) return ret; if (before_flag < 2) return ret = max(drinking_wine(index + 1, before_flag + 1, 0), drinking_wine(index + 2, 1, 1)) + alchol[index]; else return ret = max(drinking_wine(index + 2, 1, 1), ret) + alchol[index]; } int main() { cin >> cup_count; alchol = vector<int>(10002, 0); for (int j = 0; j < cup_count; j++) cin >> alchol[j]; cache = vector<vector<int>>(2, vector<int>(10002, 0)); cout << max(drinking_wine(0, 1, 0), drinking_wine(1, 1, 1)) << endl; }

구글을 찾아보았는데 생각해보니.. 한잔도 마시지 않는 경우가 있다는 것을 알았다..

한잔도 마시지 않는 경우라니! 이건 어떻게 저장해야할지 몰랐다. 

따라서 그냥 배열을 3차배열로 변경하였다.

그리고 max값에서 한개를 더 추가하였다. 바로 마시지 않고 넘어갈 때이다.

그랬더니 정답이 떴다.

사실 답을 배낄려고 했다가..한번 해보자 한건데 됬다..

drinking_wine 함수 안을 살펴보면 index가 cup_count보다 크면 현재 alchol을 return 하였다.

(top_down방식 사용)

아 만약 cup_count보다 크면 배열을 넘어선다 하지만 미리 10002개의 배열을 만들어놓았다.

왜냐하면 문제의 최대 와인잔의 개수는 10000개이기 때문이다. 그리고 0으로 초기화를 시켜놓았다.

만약 -1로 초기화를 시켜놓으면 현재 답에서 -1을 더해주는 것이기 때문에 답이 달라지게 된다.

그리고 cache에서 flag index값이 현재 있는지를 확인하고 존재한다면 return한다.

before_flag가 무엇이냐면 사실 이름을 잘 못지었다.

before_flag는 현재 얼마나 연속적으로 와인을 마셨는지를 count하는 것이다.

이 함수의 전체적인 아이디어는

현재 잔을

1. 안 마실수도 있고

2. 마실 수도 있고

 2-1. 마시는 대신 다음잔도 마실수도 있고

 2-2. 마시는 대신 다음잔을 안 마실 수도 있고

만약 before_flag가 2 즉 연속으로 두잔을 마셨으면 2잔뒤의 값을 마셔준다.

main에서도 3개로 나누어서 max값을 계산한다.

max(drinking_wine(0, 1, 0), max(drinking_wine(0, 1, 1), drinking_wine(1, 1, 2)))

세번째 성공

#include <iostream> #include <fstream> #include <vector> #include <algorithm> using namespace std; int cup_count; vector<int>alchol; vector<vector<int>> cache; int drinking_wine(int index, int before_flag, int flag) { if (index >= cup_count) return alchol[index]; int&ret = cache[flag][index]; if (ret != 0) return ret; if (before_flag < 2) return ret = max(drinking_wine(index + 1, before_flag, 0), max(drinking_wine(index + 1, before_flag + 1, 1) + alchol[index], drinking_wine(index + 2, 1, 2) + alchol[index])); else return ret = max(drinking_wine(index + 2, 1, 2), ret) + alchol[index]; } int main() { cin >> cup_count; alchol = vector<int>(10002, 0); for (int j = 0; j < cup_count; j++) cin >> alchol[j]; cache = vector<vector<int>>(3, vector<int>(10002, 0)); cout << max(drinking_wine(0, 1, 0), max(drinking_wine(0, 1, 1), drinking_wine(1, 1, 2))) << endl; }