[백준 2156] 포도주 시식 문제풀이

위 로고를 누르면 해당 문제로 이동합니다.

1차 풀이 (2018-08-14, 2060 KB, 4 MS)

 부분 문제로 나눌 수 있을까? 

K개의 포도주 잔이 있을 때, 한번에 해결하기 힘들다면

각 선택별로 부분 문제를 만들어 해결해보자고 생각했다.

각 문제에서 가능한 선택마다 부분 문제를 만들었을 때,

• 각 문제는 일정한 입력에 대해 일정한 결과만을 출력하며,

• 원래 문제와 부분 문제는 서로 독립적이고, (앞의 선택이 뒤의 선택에 영향을 주지 않음)

• 부분 문제가 최적일 때, 원래 문제도 최적으로 구해질 수 있으므로,

최적 부분 구조를 가진 동적 계획법으로 풀 수 있다.

 제한을 올바르게 이해하고 있었나? 

주어진 제한은 "연속으로 3잔 마시는 것은 안된다" 이지만,

연속으로 고르지 않아도 된다는 점에 유의해야 한다.

만약 위의 사항을 염두하지 못하고 알고리즘을 짜면,

다음의 테스트 케이스에서 오답을 낼 것 이다.

10  10  1  1  10  10

 → 최적은 1, 2, 5, 6 번째 잔을 선택하는 것.

 각 경우마다 가능한 선택은 무엇인가? 

동적 계획법으로 정확하게 문제를 풀기 위해서는

• 앞의 선택으로 인해 뒤의 선택에 영향이 있으면 안되고,
• 중복되거나 누락되는 선택방법이 있어서는 안된다.

위의 조건을 만족하는 선택방법은 다음과 같다.

• 0개 선택. 1개 건너뜀.
• 1개 선택. 1개 건너뜀.
• 2개 선택. 1개 건너뜀.

3개 이상을 선택하는 방법은 제약에 위반된다.

 재귀로 풀까, 반복으로 풀까? 

재귀는 큰 문제를 작은 문제로 쪼개면서 문제를 풀고, (해결한 작은 문제 조각들은 캐싱하여 중복계산을 방지한다.)

반복은 가장 처음부터 차근차근 문제를 푼다. (푼 문제의 답은 캐싱하여 다음 문제를 풀 때 활용한다.)

부분 문제가 비약적으로 많아지는 문제의 경우에는

함수 호출 스택에 오버헤드가 발생하므로,

왠만하면 재귀를 사용하지 않고 반복으로 풀고 싶었다.

10000개의 포도주가 주어졌을 때,

각 선택은 많아도 2개의 포도주 밖에 선택하지 못하지만,

생성되는 부분문제는 무려 3개다.

말로 설명하자니 잘 모를 수 있겠지만,

트리로 그리면 큰 숲이 펼쳐질 것 이다.

 반복으로 문제를 풀려면, 

반복으로 문제를 푸는 것은,

앞에서부터 차근차근 문제를 풀어나가는 대신,

앞선 문제의 답에서 다음 문제의 답을 도출하는 것 이다.

n번째부터 0, 1, 2개를 선택해야 할 때,

앞 뒤 문제의 연관성을 이해하면서 구현한다.

	#include <iostream>
	#include <algorithm>
	using namespace std;
	int N = 0;
	int V[10003];
	int ret[10003]; // ret[n] : n까지 골랐을 때, 최대로 마실 수 있는 포도주 량.
	int main()
	{
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> V[i];
	for (int i = 1; i <= N; i++)
	{
	//! i부터 0개 선택,
	ret[i] = max(ret[i], ret[i - 1]);
	//! i부터 1개 선택,
	ret[i + 1] = max(ret[i + 1], ret[i - 1] + V[i]);
	//! i부터 2개 선택,
	ret[i + 2] = max(ret[i + 2], ret[i - 1] + V[i] + V[i + 1]);
	}
	//! 알고리즘이 N+2만큼 침범한다.
	//! 답은 ret[N ... N+2] 안에 있다.
	int M = 0;
	for (int i = N; i <= N + 2; i++) M = max(M, ret[i]);
	cout << M;
	}

view raw bj2156.cpp hosted with ❤ by GitHub

2차 풀이 (2018-08-16, 2060 KB, 0 MS)

 어디에서 시간이 오래걸릴까? 

나름 최적화한 알고리즘(1차풀이)에서 4 MS의 오차가 발생한것에 의문을 품었다.

원인을 알기위해 다른 사람들이 어떻게 문제를 풀었는지 체크해봤는데,

별 다른 차이점을 알지 못했다.

가장 큰 차이점이라고 해봐야,

슬라이딩 윈도우 기법을 사용하여 배열의 크기를 3~5 정도로 줄인 것?

그렇다면 메모리 사용량에서만 차이가 나야지, 시간의 차이는 날 수 없다.

어디서 4 MS의 지연이 발생할까?

 cin, cout은 동기화 과정이 포함되어 있다. 

C++에서 사용하는 cin, cout은 stdio와 동기화 과정이 포함되어 있다.

즉, 입출력 과정에서 시간이 지연되었다고 생각할 수 있고,

대체로 10,000개의 입력당 4 MS 정도가 지연된다.

stdio와 동기화 과정을 풀어주는 명령어를 적어주면,

예상대로 0 MS로 줄어드는 결과를 확인할 수 있었다.

이에 대한 자세한 내용은 여기에 나와있다.

	#include <iostream>
	#include <algorithm>
	using namespace std;
	int N = 0;
	int V[10003];
	int ret[10003]; // ret[n] : n까지 골랐을 때, 최대로 마실 수 있는 포도주 량.
	int main()
	{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> V[i];
	for (int i = 1; i <= N; i++)
	{
	//! i부터 0개 선택,
	ret[i] = max(ret[i], ret[i - 1]);
	//! i부터 1개 선택,
	ret[i + 1] = max(ret[i + 1], ret[i - 1] + V[i]);
	//! i부터 2개 선택,
	ret[i + 2] = max(ret[i + 2], ret[i - 1] + V[i] + V[i + 1]);
	}
	//! 알고리즘이 N+2만큼 침범한다.
	//! 답은 ret[N ... N+2] 안에 있다.
	int M = 0;
	for (int i = N; i <= N + 2; i++) M = max(M, ret[i]);
	cout << M;
	}

view raw bj2156_2.cpp hosted with ❤ by GitHub