백준 3060번 욕심쟁이 돼지 :: 마이구미

이번 글은 백준 알고리즘 문제 3060번 "욕심쟁이 돼지" 를 다뤄본다.

난이도 있는 문제가 아니지만, 정답률은 30%이기 때문에, 함정이 있을거라 예측할 수 있다.

문제 풀이는 나머지 연산을 활용하는 문제라고 볼 수 있다.

예를 들어, 현수가 1번부터 6번까지 돼지에게 각각 3, 2, 7, 1, 5, 4만큼 밥을 주었다면, 2번 돼지는 첫 날 받은 양 2에다 양쪽과 맞은편 돼지가 받은 양 15(3+7+5)만큼을 더해 17만큼 받기를 원한다.

마음씩 좋은 농부 박현수는 이런 돼지의 요구를 모두 들어주려고 한다. 매일 현수의 집에 신선한 사료가 N만큼 배달된다. 사료의 유통기한은 하루이기 때문에, 남은 사료는 모두 폐기한다.

첫 날 돼지들이 먹었던 양이 주어졌을 때, 현수가 6마리의 돼지들의 요구를 들어줄 수 없게 되는 날이 몇 번째 날인지 구하는 프로그램을 작성하시오.

문제는 이해하기 어렵지 않다.

본인도 처음에는 단순히 순수하게 생각하여 접근하였다.

(문제는 맞추고, 그 뒤에 코드를 바꿔도 되니까....)

int pig1 = array[1] + array[2] + array[6] + array[4];
int pig2 = array[2] + array[1] + array[3] + array[5];
int pig3 = array[3] + array[2] + array[4] + array[6];
int pig4 = array[4] + array[3] + array[5] + array[1];
int pig5 = array[5] + array[4] + array[6] + array[2];
int pig6 = array[6] + array[1] + array[5] + array[3];

위와 같이 돼지 여섯마리를 각각 노가다로 넣는 것이다.

코드가 어찌됐든 정답일 거라 생각했지만, 틀렸다.

곰곰히 생각해보니, 함정이 숨어있었다.

입문자들이 알고리즘 문제에서 가장 많이 하는 실수는 범위 초과가 된다.

이번 문제 또한 사실 상 int 범위를 초과하게 된다.

이러한 함정 때문에 정답율이 낮은 것이라고 볼 수 있다.

문제는 해결했으니, 코드를 바꿔보자.

예전에 조세퍼스 관련 문제를 다룰 때도 나머지 연산을 설명했다.

규칙이 있다면, 나머지 연산으로 충분히 만들 수 있다고 언급했다.

// (i + 1) % 6 => 오른쪽, (i + 3) % 6 => 바라보는쪽, (i + 5) % 6 => 왼쪽
array[i] + array[(i + 1) % 6] + array[(i + 3) % 6] + array[(i + 5) % 6];

전체 소스는 아래 Github URL을 참고하길 바란다.

백준 알고리즘 문제 3060번 "욕심쟁이 돼지" 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/math/3060.java