백준 1461(도서관) 맞왜틀?

맞는데 왜 틀렸지? 라는 생각을 갖게된다. 나의 논리가 완벽하기에 나를 너무 믿기에 자꾸 틀린걸 알면서도 제출버튼을 클릭하고 제출한다. 

 

알고리즘 문제를 풀다보면 논리의 허점을 찾기가 정말 힘들다. 단순 예제를 만들어서 확인해볼 생각도 안 하고, 확인했던 것만 확인하고 틀린다. 멍청 

 

이 문제도 그랬다 

그냥 결론은 딱히 없고 예제좀 제대로 넣고 풀어보자 처음부터 논리적으로 완벽하긴 더 힘들거 같으니깐 제발

 

https://www.acmicpc.net/problem/1461

1461번: 도서관

N권의 책을 옮기는데 한번에 M권을 옮길 수 있다. 

여기서 책을 다 옮겼을 때의 최소거리를 구하는 문제이다. 

 

좀만 생각해보면 책은 계속 0에 있으니 0에서의 최대거리에서 멈출 때가 이동거리가 적을 때이고,

더 먼곳은 먼곳끼리 한번에 옮길때가 이동거리를 줄일 수 있다. 

 

그래서 양/음의 위치를 배열 두개로 나누어서 정렬하였고, 

 

3 2

4 8 12 

이렇게 예제가 주어졌다고 하면 

 

8까지 왔다가 12까지 가는 것 보다는 

4까지 왔다가 12까지 가는 게 더 적은 거리이므로 

 

권수를 이동가능 권수로 나눈 나머지만큼 먼저 처리하고

나머지 이동가능 권수의 배수를 차례대로 처리하는 코드로 짰다. 

 

여기서 배열의 index와 권수와는 +1 차이가 있으므로 주의해서 코드를 짰다.

#include<iostream>
#include<algorithm>
#define MAX 10000
using namespace std;

int N, M, r=0, l=0, a, res=0, rem, mul;
int r_book[MAX] = { 0 };
int l_book[MAX] = { 0 };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		cin >> a;
		if (a > 0) r_book[r++] = a;
		else l_book[l++] = -a;
	}
	sort(r_book, r_book + r);
	sort(l_book, l_book + l);
	if (r_book[r-1] > l_book[l-1]) {
		rem = l % M - 1;
		mul = l / M;
		if(rem>=0)
			res += (l_book[rem] * 2);
		while (mul--) {
			rem += M;
			res += (l_book[rem]*2);
		}
		rem = r % M - 1;
		mul = r / M;
		if (rem >= 0) {
			if (rem == (r-1)) res += r_book[rem];
			else res += (r_book[rem] * 2);
		}
		while (mul--) {
			rem += M;
			if (mul == 0) {
				res += r_book[rem];
			}
			else {
				res += (r_book[rem] * 2);
			}
		}
		cout << res ;
		return 0;
	}
	else {
		rem = r % M - 1;
		mul = r / M;
		if (rem >= 0)
			res += (r_book[rem] * 2);
		while (mul--) {
			rem += M;
			res += (r_book[rem] * 2);
		}
		rem = l % M - 1;
		mul = l / M;
		if (rem >= 0 )
			if (rem == (l-1)) 
				res += l_book[rem];
			else
				res += (l_book[rem] * 2);
		while (mul--) {
			rem += M;
			if (mul == 0) {
				res += l_book[rem];
			}
			else {
				res += (l_book[rem] * 2);
			}
		}
		cout << res ;
		return 0;
	}
}