[BOJ]2847게임을 만든 동준이 : 그리디 알고리즘 C++ 문제 해결 및 코드

역시 '최소한' 즉 최적의 답을 찾는 그리디 알고리즘 문제, 반례를 찾지 못하는 틀린 코드만 계속 만들어 내었던 문제인 것 같다. 먼저 생각한 알고리즘은 다음과 같다. 

// 레벨 점수를 list에 '반대로' 담아 레벨이 높은 순대로 정렬한다.
while(비교할 하위 레벨이 NULL이 아닌 경우
	if(list[i] > list[i+1])
		넘어가
	else
		count+=(list[i + 1] - list[i] + 1)
		list[i+1] = list[i] - 1;
	i++;

이런 의사 코드로 만들어진 코드는 다음과 같다. 

int main()
{
	int count = 0;
	int list[100] = { NULL };
	int N;
	cin >> N; //4 
	for (int i = 0; i < N;i++)
	{
		cin >> list[N - i - 1];
	}
	int i = 0;
	while (list[i + 1] != NULL)
	{
		if (list[i] <= list[i + 1])
		{
			count += (list[i + 1] - list[i] + 1);
			list[i + 1] = list[i] - 1;
		}
		i++;
	}

	cout << count << endl;

	return 0;
}

왜 틀린걸까 ? - ? 아직까지도 의문

아는 사람은 댓글 써주세요 제발

처음엔 NULL값 때문에 한번 오류 뜨고 NULL 값 고려해서 다시 코드를 짰는데 도 . .. . 틀렸다고 뜬다. 

 

아무튼 그래서 알고리즘을 아예 다시 짰다

일단 배열에 거꾸로 넣는 것은 버리고 입력 값 순서대로 넣되 for문에서 인접한 값을 비교하는 것은 뒤에서부터, 즉 레벨이 높은 순대로 진행한다. 그리고 while문을 써서 현재 레벨의 점수가 하위 레벨의 점수보다 높으면 break를 하고, else문에서 배열의 값--; count++; 를 실행해 점수를 내린다.

#include <iostream>
using namespace std;

int main()
{
	int N; cin >> N;
	int list[101] = { NULL };
	int count = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> list[i];
	}
	for (int i = N - 1; i > 0; i--)
	{
		while (true)
		{
			if (list[i] > list[i - 1]) 
				//높은 레벨의 점수가 더 크면
				break; // 넘어가고
			else //낮은 레벨의 점수가 더 크거나 같으면 
			{
				list[i - 1]--;
				count++;
			}
		}
	}
	cout << count << endl;
	return 0;
}

최종 해결한 코드..

컴파일 에러는 오타다^^;