티스토리 뷰
백준 온라인 저지의 2839번 문제.
언제나처럼 침대에 누워서 폰 만지작거리면서 타임라인 쭉 넘겨보고 있었는데, 누가 간단해보이는데 은근 어렵다며 이 문제를 올렸다.
배달해야 할 설탕의 무게 N (kg) 이 주어졌을 때, 3kg짜리 봉지랑 5kg짜리 봉지를 가지고 최소한의 봉지만 사용해서 배달하는 방법을 찾는 문제다.
'3x + 5y = N을 만족하는 (x+y) 의 최소값을 구하라' 로도 표현할 수 있다.
1) 내가 푼 방법
문제를 보고 일단 딱 든 생각은 최대한 5kg짜리 봉지를 많이 쓰고 싶다. 3kg짜리 봉지를 생각하지 말고 5kg짜리에 초점을 맞춰보면, N을 5로 나누면 5kg짜리 봉지 몇 개를 쓸 수 있을지 알 수 있겠다.
몇 개의 예시를 생각해보자.
50kg -> 5kg * 10개
51kg -> 5kg * 10개, 1kg가 남음
52kg -> 5kg * 10개, 2kg가 남음
53kg -> 5kg * 10개, 3kg * 1개
54kg -> 5kg * 10개, 3kg * 1개, 1kg가 남음
55kg -> 5kg * 11개
50kg, 53kg인 경우엔 상관이 없는데 나머지 케이스는 1kg, 2kg짜리 봉지가 없기 때문에 문제가 된다. 3kg짜리를 써야할 것 같은데, 가능한 적은 봉지를 쓰려면 5kg짜리를 최대한 적게 빼고 3kg짜리로 대신해야 할 것 같다. 그럼 이 문제가 되는 케이스들에서 5kg짜리를 3kg짜리로 대신하려면 5kg짜리를 몇 개나 빼야할까? 먼저 5kg짜리 하나를 빼본다.
51kg -> 5kg * 9개 + 6kg -> 6kg는 3kg * 2개로 대체 가능
52kg -> 5kg * 9개 + 7kg
54kg -> 5kg * 9개 + 9kg -> 9kg는 3kg * 3개로 대체 가능
52kg인 경우는 5kg짜리 하나를 빼도 여전히 3kg짜리만으로 대체가 안된다. 그럼 하나 더 빼본다.
52kg -> 5kg * 8개 + 12kg -> 12kg는 3kg * 4개로 대체 가능
50kg~55kg의 예시에 대해서 생각해 봤는데, 56~60kg / 61~65kg / ... 등 다른 구간에서도 이게 성립할까?
56kg -> 5kg * 10개 + 6kg (51kg의 사례에서 5kg짜리 봉지만 하나 늘어남)
57kg -> 5kg * 9개 + 12kg (52kg의 사례에서 5kg짜리 봉지만 하나 늘어남)
큰 봉지가 5kg짜리기 때문에 5의 배수마다 같은 케이스가 반복되는 것이다. 이를 일반화하면 이렇게 쓸 수 있겠다.
N % 5 == 0 이면: (N/5) 개
N % 5 == 1 이면: (N/5) - 1 + 2 개
N % 5 == 2 이면: (N/5) - 2 + 4 개
N % 5 == 3 이면: (N/5) + 1 개
N % 5 == 4 이면: (N/5) - 1 + 3 개
그냥 +1개, +2개라고 써도 되지만 5kg짜리를 빼고 3kg짜리를 쓰는걸 좀 더 명확하게 보여주기 위해서 저렇게 썼다.
단 이 규칙이 적용되지 않는 구간이 있다. N이 한자리 수인 구간인데, 5kg짜리 봉지를 빼는 부분에서 눈치채야 할 게 N/5가 0이나 1인 경우 빼면 마이너스가 되어버린다. 5kg짜리를 음수개 쓰고 3kg짜리로 나머지를 채운다는 것은 있을 수 없는 일이다. 그러므로 이런 케이스에는 제약조건을 줘야 한다.
문제 조건을 보면 5kg, 3kg짜리 봉지만으로 정확히 Nkg를 만들 수 없는 경우엔 -1을 출력하라고 되어있다. 바로 그런 케이스다. 어떻게 해도 3과 5의 조합으로 만들 수 없는 수들인 1, 2, 4, 7이 해당된다.
이 내용을 코드로 옮겨적으면 이렇다.
2) 다른 사람의 풀이
뭔가 생각나는대로, 야매로 푼 것 같은 기분이었기에 다른 방법이 있겠지 싶어 인터넷을 찾아봤다. 정석적인 풀이는 역시 좀 다르긴 하더라.
5kg짜리를 최대한 쓰고 안되는만큼 3kg짜리로 대체한다는 기본 아이디어는 같은데, 규칙을 다 찾아서 넣어주는게 아니라 반복문을 돌면서 N을 5의 배수가 될 때까지 3씩 빼는 방법이었다. 3씩 빼다가 나오는 첫번째 5의 배수가 5kg짜리만으로 만들 수 있는 최적의 수라는 것이고, 3을 뺀 횟수만큼 3kg짜리 봉지를 쓴 것이 된다.
얼핏 보면 쉬워보이는 문제가 정답률이 낮길래 혹시 DP 같은걸 써야하는 문젠가? 싶었는데 그런건 아니어서 약간 김빠지는 느낌이었다... ()