[BOJ 1461 / C++] 도서관

문제

조건을 충족한 상태로 최소 비용으로 일을 수행시켜야 함. (그리디)

문제 페이지

키포인트

• 음수와 양수를 따로 고려해주면 수월하다. (각각을 다른 배열에 저장)

• 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다가 힌트이다.

코드

배열 내부의 변화를 체크하기 위해 0으로 바꾸어주는 부분이 포함되어 있다.

#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

int book[51];
int N, tmp, M, check = 0;
int cnt = 0;
int walk = 0;

int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		cin >> book[i];
	}

	sort(book, book + N);

	// 맨 마지막에 가는 위치는 다시 돌아오지 않아도 되므로 가장 많은 비용이 드는 곳으로 미리 계산해 놓는다.
	if (abs(book[0]) <= abs(book[N-1])) {  
		walk += abs(book[N-1]);
		for (int i = 0; i < M; i++) {
			if ((N - i - 1) < 0) break; // Out of Bounds 방지
			if (book[N-i-1] > 0) {
				book[N-i-1] = 0;  // 예를 들어, M이 2인데 -5 -4 11 과 같이 나오면 11만 들어가야 함.
				cnt++;
			}
		}
		N -= cnt;
		cnt = 0;
	}
	else {
		walk += abs(book[0]);
		for (int i = 0; i < M; i++) {
			if (book[i] < 0) {
				book[i] = 0;
				cnt++;
			}
		}
		check = check + cnt;
		cnt = 0;
	}

	// 배열의 앞부분부터 체크
	while ((check - N) < 0) {
		for (int i = check; i < N; i++) {
			if (book[i] < 0) {  // 음수의 경우
				walk += abs(book[i]) * 2;

				for (int j = 0; j < M; j++) {
					if (book[i+j] < 0) {
						book[i+j] = 0;
						cnt++;
					}

				}
				check += cnt;
				cnt = 0;
				break;
			}
			else {
				walk += abs(book[N - 1]) * 2;

				for (int j = N - 1; j > N - 1 - M; j--) {
					if (j < 0)break;  // Out of Bounds 방지
					if (book[j] >= 0) {
						book[j] = 0;
						cnt++;
					}
				}
				N -= cnt;
				cnt = 0;
				break;
			}
		}
		//cout << walk << endl;
	}

	cout << walk << endl;
	return 0;
}

느낀점

오랜만에 풀어서 그런지 실수가 많았다.

음수와 양수를 다른 배열에 담아줬으면 수월했을텐데 아쉬운 부분이다.

• 백준 런타임 에러

  • M이 N보다 커질 때를 고려하지 않아서 생긴 문제였음.

  • 위 코드를 보면 주석으로 out of bounds방지를 위한 라인이 있다.

  • 저 코드가 없다면 배열의 범위를 벗어난 부분을 비교하려고 해서 발생하는 문제이다.