어느 한적한 섬에 식료품점이 단 하나 있다고 가정해 봅시다. 이 가게는 일요일을 제외하고는 항상 영업합니다. 이 문제에서는 다음과 같은 값들을 입력으로 받습니다.
- N — 하루에 살 수 있는 최대 식량의 양
- S — 생존해야 하는 총 일수
- M — 하루 생존에 필요한 식량의 양
오늘이 월요일이고, 앞으로 S일 동안 생존해야 한다고 가정할 때, 우리가 생존이 가능한지 여부를 확인해야 합니다. 생존이 가능하다면, 식량을 구매해야 하는 최소 일수도 함께 구해야 합니다.
문제 예시
예를 들어 입력값이 S = 12, N = 24, M = 3이라면 결과는 True이며, 식량을 사야 하는 최소 일수는 2일입니다. 그 이유는 24단위의 식량으로 현재 월요일부터 다음 월요일까지 8일 동안 생존할 수 있고, 이후 12단위를 추가로 구매해 나머지 4일을 버틸 수 있기 때문입니다.
접근 방법
이 문제는 다음 논리로 해결할 수 있습니다.
- 생존 불가 조건: (N × 6 < M × 7 이면서 S > 6) 또는 M > N인 경우 False를 반환합니다.
→ 한 주(7일) 중 6일만 구매 가능하므로, 6일간 살 수 있는 최대 식량(N×6)조차 일주일 치 필요량(M×7)보다 적으면 일주일을 넘기는 생존은 불가능합니다. 또한 하루에 살 수 있는 양(N)보다 하루 필요량(M)이 크면 당연히 생존할 수 없습니다. - 생존 가능한 경우: 총 필요 식량(M × S)을 하루 최대 구매량(N)으로 나눈 몫을 count로 계산하고, 나누어 떨어지지 않으면 올림 처리를 위해 count에 1을 더합니다.
- 마지막으로 True와 count를 반환합니다.
Python 코드 구현
아래 예시 구현을 통해 더 잘 이해해 보겠습니다.
def solve(S, N, M): if ((N * 6) < (M * 7) and S > 6) or M > N: return False else: count = (M * S) // N if ((M * S) % N) != 0: count += 1 return (True, count) S = 12 N = 24 M = 3 print(solve(S, N, M))
입력
12, 24, 3
출력
(True, 2)
정리
이 알고리즘의 시간 복잡도는 O(1)로, 어떤 입력값이든 상수 시간 안에 결과를 얻을 수 있습니다. 핵심은 두 가지입니다. 첫째, 일요일 휴무로 인한 주간 공급 제약(N × 6 ≥ M × 7)을 검사하는 것, 둘째, 총 필요량을 일일 최대 구매량으로 나누어 올림 처리함으로써 최소 구매 일수를 구하는 것입니다. 이런 유형의 그리디·수학 기반 문제는 코딩 테스트에서 자주 등장하니 개념을 확실히 익혀두면 유용합니다.