[BOJ]1449수리공 항승 : 그리드 알고리즘 C++ 해결 코드와 설명

처음엔 테이프를 이어붙이는 동작을 어떻게 프로그램에서 표현할 수 있을까를 고민했다.  '0.5'를 표현해야 한다는 고정관념에 사로잡혀 한참을 고민했다. 

그러다 배열의 한 메모리를 '구멍' 자체로 생각하니 0.5 같은 건 생각할 필요가 없어졌고, 배열과 파이프를 동일시하여 생각하기로 하였다.  구현 알고리즘과 의사코드는 다음과 같다. 

1. 파이프 배열을 생성해 구멍이 생긴 부분의 값을 true로 바꾸어준다. 

2. for문을 배열의 처음부터 순차적으로 돌며 맨 처음 true인 부분을 만나면 먼저 false처리 해주고, 그 부분에서 테이프의 길이만큼의 범위에서 true 인 부분이 있는지 이중 for문을 통해 관찰한다. 

3. 만약 이중 for문에서 물이 새는 부분이 또 있으면 그 부분을 false 처리하여 중복 동작을 방지한다. 

4. 중복되는 부분까지 모두 테이프를 붙였으면 count++를 해주어 테이프의 개수를 증가시킨다.

 

- 의사코드

/*
* a = max(list) // 물이 새는 곳 중에 가장 멀리 있는 곳
* for(int i = 0; i <= a; i++)
*	if(list[i] == true) //물이 새는 곳이라면
*		for(int j = i; j < i + (L - 1); j++) //테이프 길이 만큼 돌면서
*			if(list[j] == true)
*				list[j] = false;
*		count++; //테이프 길이만큼 겹치는 부분까지 전부 하나의 테이프로 붙임
*/

- 시행착오

 

#include <iostream>
using namespace std;

int main()
{
	bool list[1001] = { false };
	int count = 0;
	int L, N;
	cin >> N >> L; //물이 새는 곳의 개수와 테이프의 길이 입력
	int a; int last_index; // 물이 새는 곳의 인덱스와 마지막 물이 새는 곳의 인덱스를 담을 변수 선언
	for (int i = 0; i < N; i++)
	{
		cin >> a;
		list[a] = true; // 물이 새는 곳을 인덱스로 true로 변환해준다. 
		last_index = a;
	}
	//처음부터 물이 새는 곳이 끝나는 곳까지 for문
	for (int i = 0;i <= last_index; i++)
	{
		if (list[i] == true) //물이 새는 부분일 때
		{	
            list[i] = false;
            //물이 새는 부분에서 테이프의 길이만큼의 영역까지 탐색
			for (int j = i+1; j <= i + (L - 1); j++)
			{
				if (list[j] == true) // 물이 새는 부분이면
				{
					list[j] = false; // 테이프로 붙인 상황이므로 false로 변환
				}
			}
			count++; // 테이프 길이만큼 겹치는 부분까지 전부 하나의 테이프로 붙임
		}
	}
	cout << count << endl;
	return 0;

}

list의 배열의 크기를 1000으로 설정해 L이나 물이 새는 곳의 위치가 1000으로 입력되었을 때 에러가 뜨므로 이를 1000보다 큰 수로 설정해 오류를 해결했다. 

굳이 배열의 끝까지 for문을 돌릴 필요는 없고 RuntimeError의 위험이 있으니 last_index 변수를 통해 마지막으로 물이 새는 곳의 인덱스를 담으려 했다. 

5 2 

1 2 3 4 5

다음과 같이 오름차순으로 입력값을 넣지 않고 

5 2 

5 4 3 2 1

다음과 같이 내림차순으로 입력값을 넣었을 경우에는 1이 last_index 값으로 들어가 잘못된 값이 출력됨을 알 수 있었다. 

 

수정한 코드는 다음이다.

#include <iostream>
using namespace std;

int main()
{
	bool list[1001] = { false };
	// vector <bool> list = { false };//물이 새는지 여부를 담을 파이프 vector
	int count = 0;
	int L, N;
	cin >> N >> L; //물이 새는 곳의 개수와 테이프의 길이 입력
	int a; int last_index; // 물이 새는 곳의 인덱스와 마지막 물이 새는 곳의 인덱스를 담을 변수 선언
	for (int i = 0; i < N; i++)
	{
		cin >> a;
		list[a] = true; // 물이 새는 곳을 인덱스로 true로 변환해준다. 
		// last_index = a;
	}
	//처음부터 물이 새는 곳이 끝나는 곳까지 for문
	for (int i = 0;i <= 1000; i++)
	{
		if (list[i] == true) //물이 새는 부분일 때
		{	//물이 새는 부분에서 테이프의 길이만큼의 영역까지 탐색
			list[i] = false;
			for (int j = i + 1; j <= i + (L - 1); j++)
			{
				if (list[j] == true) // 물이 새는 부분이면
				{
					list[j] = false; // 테이프로 붙인 상황이므로 false로 변환
				}
			}
			count++; // 테이프 길이만큼 겹치는 부분까지 전부 하나의 테이프로 붙임
		}
	}
	cout << count << endl;
	return 0;
}

그래서 그냥 last_index 변수를 쓰지 않고 처음부터 배열 끝까지 for문을 돌렸다. 음 런타임 에러가 뜨길래 해당 for문에서 시간 초과가 뜬거라 생각했다. 어떻게든 last_index의 값을 지정해 이 변수를 이용해 for문을 돌려야한다고 생각했다.

	for (int i = 1;i < 1000; i++)
	{
		if (list[i] == true)
		last_index = i;
	}

중간에 이 코드를 넣었으나 역시 동일하게 시간초과 에러가 떴다. 

bool list[1010] = { false };

혹시 배열 인덱스 초과 에러일까 list의 배열 크기 자체를 늘려버려도 여전히 런타임 에러 ㅎㅎ

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

그래서 while문을 써서 '1000'이라는 숫자를 쓰지않고 last_index변수를 초기화할 수 있는 방법을 생각했다.

애초에 배열 안에서 true의 개수는 N으로 정해져 있으므로 배열을 처음부터 돌면서 temp변수가 N이 될때까지 while문을 돌도록 하고 temp변수가 N이 되기 직전, if문에서 last_index = i로 초기화하며 while문을 빠져나가도록 한다. 그렇게 해서 해결 된 것이 다음 코드이다

 

 

- 최종 해결 코드

#include <iostream>
using namespace std;

int main()
{
	bool list[1010] = { false };
	int count = 0;
	int L, N;
	cin >> N >> L; //물이 새는 곳의 개수와 테이프의 길이 입력
	int a; int last_index; // 물이 새는 곳의 인덱스와 마지막 물이 새는 곳의 인덱스를 담을 변수 선언
	for (int i = 0; i < N; i++)
	{
		cin >> a;
		list[a] = true; // 물이 새는 곳을 인덱스로 true로 변환해준다. 
		// last_index = a;
	}
	//마지막으로 true인 인덱스를 last_index변수에 담는다. 
	int temp = 0;
	int i = 0;
	while (temp != N)
	{
		if (list[i] == true)
		{
			temp++;
			last_index = i;
		}
		i++;
	}
	//처음부터 물이 새는 곳이 끝나는 곳까지 for문
	for (int i = 1;i <= last_index; i++)
	{
		if (list[i] == true) //물이 새는 부분일 때
		{	//물이 새는 부분에서 테이프의 길이만큼의 영역까지 탐색
			list[i] = false;
			for (int j = i + 1; j <= i + (L - 1); j++)
			{
				if (list[j] == true) // 물이 새는 부분이면
				{
					list[j] = false; // 테이프로 붙인 상황이므로 false로 변환
				}
			}
			count++; // 테이프 길이만큼 겹치는 부분까지 전부 하나의 테이프로 붙임
		}
	}
	cout << count << endl;
	return 0;
}

 

후회없는 시행착오였다...