[백준 2885: 초콜릿 식사] 파이썬 풀이
문제
학교 근처 편의점에 새 초콜릿이 들어왔다. 이 초콜릿은 막대 모양이고, 각 막대는 정사각형 N개로 이루어져 있다. 초콜릿의 크기(정사각형의 개수)는 항상 2의 제곱 형태이다. 즉, 1, 2, 4, 8, 16, ...개의 정사각형으로 이루어져 있다.
상근이는 점심식사로 초콜릿을 먹는다. 이때, 적어도 K개 정사각형을 먹어야 남은 수업을 졸지 않고 버틸 수 있다. 상근이의 친구 선영이도 초콜릿을 좋아한다. 선영이는 초콜릿은 돈을 주고 사기 아깝다고 생각하기 때문에, 상근이가 주는 초콜릿만 먹는다.
상근이는 막대 초콜릿를 하나 산 다음에, 정확하게 K개 정사각형이 되도록 초콜릿을 쪼갠다. K개는 자신이 먹고 남는 것은 선영이에게 준다.
막대 초콜릿은 나누기 조금 어렵게 되어 있어서, 항상 가운데로만 쪼개진다. 즉, 정사각형이 D개 있는 막대는 D/2개 막대 두 조각으로 쪼개진다.
K개 정사각형을 만들기 위해서, 최소 몇 번 초콜릿을 쪼개야 하는지와 사야하는 가장 작은 초콜릿의 크기를 구하는 프로그램을 작성하시오. 상근이는 초콜릿을 하나만 살 수 있다. 꼭 한 조각이 K개일 필요는 없고, 여러 조각에 있는 정사각형을 합쳤을 때 K개이면 된다.
입력
첫째 줄에 K가 주어진다. (1 ≤ K ≤ 1,000,000)
출력
첫째 줄에는 상근이가 구매해야하는 가장 작은 초콜릿의 크기와 최소 몇 번 쪼개야 하는지를 출력한다.
💡 풀이 아이디어
처음에 문제가 이해가 안 가서 한참 읽어보고 이해할 수 있었는데,
예시의 k = 6을 보면, 6조각의 초콜릿을 만들기 위한 가장 작은 초콜릿의 크기는 8이고,
두 번 잘라야 2조각 + 4조각 = 6조각을 만들 수 있기 때문에 최소 2번 잘라야하므로
6 입력의 출력은 8 6이 된다.
규칙을 찾기 위해 여러 예시들을 그림을 그려가며 이해하였다..
가장 작은 초콜릿의 크기를 찾는 것은 비교적 쉬웠다.
자신보다 크거나 같은 2의 제곱수 중 가장 작은 값을 찾으면 된다.
ex) 6이면 8, 7이면 8, 8이면 8, 9이면 16, 10이면 16 …
최소 몇 번 자르는지 계산하는 것이 조금 어려웠는데..
일단 k값을 2의 제곱수로 쪼개야한다
5 = 4 + 1
6 = 4 + 2
7 = 4 + 2 + 1
쪼개다보니, 몇 까지 쪼개는지에 따라 갯수가 달라지는 규칙을 찾았다.
⇒ while문을 돌면서 값을 2로 몇 번 나눴는지 count를 해서 답을 구했다!
💻 코드
import sys
input = sys.stdin.readline
k = int(input())
square_of_2 = []
result = [] # 결과 배열 [초콜릿의 크기, 최소 횟수]
for i in range(21): # 가능한 2의 제곱들을 모두 리스트에 담음
square_of_2.append(2**i)
size = -1 # 초콜릿의 사이즈
for square in square_of_2: # 2의 제곱들을 확인하면서
if square >= k: # 가장 작으면서 k보다 큰 값을
size = square # size에 저장
break
result.append(size) # 전체 초콜릿 크기를 결과 배열에 담음
count = 0
if k == size: # K가 size값과 같으면 쪼갤 필요가 없으므로 0
result.append(0)
else:
while k>0: # k가 0보다 크면 반복
if k>=size: # k가 size보다 크면
k = k - size # size값을 빼줌
else:
size = size//2 # size를 2로 나눔
count += 1 # count 증가
result.append(count)
print(*result)# 가장 작은 초콜릿의 크기 구하기
for i in range(21): # 가능한 2의 제곱들을 모두 리스트에 담음
square_of_2.append(2**i)
size = -1 # 초콜릿의 사이즈
for square in square_of_2: # 2의 제곱들을 확인하면서
if square >= k: # 가장 작으면서 k보다 큰 값을
size = square # size에 저장
break
result.append(size) # 전체 초콜릿 크기를 결과 배열에 담음
- 2의 제곱들을 리스트에 모두 담아놓음
- 작은 값부터 확인하면서, k보다 크면 가장 작은 초콜릿의 크기
# 최소 몇 번 자르는지 구하기
count = 0
if k == size: # K가 size값과 같으면 쪼갤 필요가 없으므로 0
result.append(0)
else:
while k>0: # k가 0보다 크면 반복
if k>=size: # k가 size보다 크면
k = k - size # size값을 빼줌
else:
size = size//2 # size를 2로 나눔
count += 1 # count 증가
result.append(count)
- k가 size와 같다면, k=8일 때 8조각 모두가 필요한 것이므로, 쪼갤 필요가 없음 : 0
- 그게 아니라면, while문을 돌면서,
- k가 size보다 크면 size값을 빼주고, 그렇지 않으면 값을 2로 나눠주면서 count를 증가
(2로 몇 번 나누었는지 세서 결과로 활용)