문제
출처 : https://www.acmicpc.net/problem/1052
문제 이해
조건:
-
N개의 물병에는 1만큼의 물이 각각 담겨있습니다
-
물을 담고있는 물병의 갯수가 K개를 초과해서는 안됩니다.
-
같은양의 물을 담고있는 물병끼리는 물을 부을 수 있습니다.
-
같은양의 물을 담고있는 물병의 짝이 없고 물을 담고있는 물병의 갯수가 K개를 넘는다면 상점에서 물병을 살 수 있습니다. 이때 물병안에 있는 물의 양은 1입니다.
구할 것:
- N개의 물병을 이용해 물이 담긴 물병의 갯수 K개 이하로 만들기 위해 상점에서 산 물병의 최솟값을 구해야 합니다.
문제 접근
이 문제에서 물병을 합쳤을 때 물의 양을 한번 생각해봐야 합니다.
- 처음 물병에 들어있는 물의 양은 1
- 물의 양이 1로 동일한 물병들을 합치면 물의양은 2
- 물의 양이 2로 동일한 물병들을 합치면 물의 양은 4
- 물의 양이 4로 동일한 물병들을 합치면 물의 양은 8
결과적을 물을 합치면 2의 제곱 수열과 동일한 수열의 구조가 나타나게 됩니다.
1 -> 2-> 4-> 8
이걸로 어떻게 문제를 풀 수 있을까요?!
바로 이진수 연산입니다!
이진수 연산중에 이진수의 덧셈을 이용합니다.
-
물의 양이 1만큼 들어있는 물병끼리 합친다면 1 + 1 = 2 (0001 + 0001 = 0010) 입니다.
이때는 물병이 2개에서 1개로 줄어듭니다! -
물의 양이 2만큼 들어있는 물병끼리 합친다면 2 + 2 = 4 (0010 + 0010 = 0100) 입니다.
마찬가지로 물병이 2개에서 1개로 줄어듭니다!
이진수에서는 1, 2, 4, 8은 1이 존재하는 자리수에 따라 달라지기 때문에 물병의 갯수를 이진수로 표현했을 때 1의 갯수가 바로 물병의 양 입니다.
여기까지 이해가 안되신다면!
만약 n이 3이라고 했을 때 3은 이진수로 0011로 표현할 수 있습니다. 처음 각 물병은 1만큼의 물을 담고 있습니다. 각 물병을 이진수로 표현하면 0001(1), 0001(1), 0001(1) 입니다. 물의 양이 맞아 합칠 수 있는 물병을 합친다면 물의 양이 0010(2), 0001(1) 만큼 담고있는 2개의 병이 만들어집니다.
결국, 0010에서의 1의 개수 1, 0001에서의 1의개수 1이기 때문에 병의 개수는 2개라고 볼 수 있습니다.
정답 코드
import sys
input = sys.stdin.readline
# n: 물병의 개수, k: 물이 들어있는 물병의 최대 개수
n, k = map(int, input().strip().split())
# 물이 늘어나는 규칙: 2, 4, 8, 16(2제곱을 계속 하면서 늘어남)
cnt = 0
while bin(n).count('1') > k:
n += 1
cnt += 1
print(cnt)실패 코드 1 (시간초과)
import sys
input = sys.stdin.readline
# n: 물병의 개수, k: 물이 들어있는 물병의 최대 개수
n, k = map(int, input().strip().split())
# 어떻게?
# 짝이 맞는 병들을 다 합친다. (짝을 맞추는 함수 짝을 맞추고 병의 개수 반환하기)
# 짝을 맞춘 후 k보다 작다면 끝!
# 짝을 맞추는 함수
# 리스트 오름차순 정렬하고 맞다면 뒤에다 enqueue, 앞은 deque
bottle =[]
# 병 정보 초기화
for i in range(n):
bottle.append(1)
def merge():
length = len(bottle)
cnt = 0
# True: 바꿈 False: 바꾸지 않음
check = False
while cnt < length:
if bottle[0] == bottle[1]:
bottle.append(bottle[0] * 2)
check = True
del(bottle[0])
del(bottle[0])
cnt += 2
else:
bottle.append(bottle[0])
del(bottle[0])
cnt += 1
return check
def sol():
result = 0
while len(bottle) > k:
bottle.sort()
if merge() == False:
result += 1
bottle.insert(0, 1)
merge()
return result
print(sol())위의 코드는 물의 양이 동일한 물병들을 합치는 merge함수와 물이 담겨있는 물병의 갯수가 K개보다 작은지 확인하고 크다면 그리고 물병이 부족하다면 상점에서 사서 다시 merge하는 함수를 구현하였습니다.
문제 조건에서 N에는 최대 10,000,000의 값이 올 수 있었습니다. 결국 10,000,000이라는 값이 N에 들어오게되면 한번 merge를 하는데만 거의 5,000,000번을 돌게 됩니다... 허허..
바로 시간초과로 광탈!
실패 코드 2 (시간초과)
import sys
input = sys.stdin.readline
# n: 물병의 개수, k: 물이 들어있는 물병의 최대 개수
n, k = map(int, input().strip().split())
# 어떻게?
# 무조건 갯수를 이용해야 함
# 짝이 맞는 병들을 다 합친다. (짝을 맞추는 함수 짝을 맞추고 병의 개수 반환하기)
# 짝을 맞춘 후 k보다 작다면 끝!
# 짝을 맞추는 함수
# 리스트 오름차순 정렬하고 맞다면 뒤에다 enqueue, 앞은 deque
bottle = dict()
bottle[1] = n
# 같은 양의 물을 담고있는 물병의 물을 합치는 함수
def merge():
check = False
temp = bottle.copy()
for liter, num in temp.items():
# 홀수이면 하나가 남는다.
if num % 2 == 1 and num != 1:
if liter * 2 in bottle:
bottle[liter * 2] += num // 2
else:
bottle[liter * 2] = num // 2
bottle[liter] = 1
check = True
elif num % 2 == 0: # 짝수인 경우
if liter * 2 in bottle:
bottle[liter * 2] += num // 2
else:
bottle[liter * 2] = num // 2
del(bottle[liter])
check = True
return check
def sol():
cnt = n
result = 0
while cnt > k:
# 물을 합칠 짝이 없다면
if merge() == False:
if 1 in bottle:
bottle[1] += 1
else:
bottle[1] = 1
result += 1
sum = 0
for i in bottle.values():
sum += i
cnt = sum
return result
print(sol())마지막 이 코드는 실패 코드 1에서 설명한 코드와는 다르게 물의 양을 key, key만큼의 물의 양을 담고있는 물병의 갯수를 value로 갖고 있는 딕셔너리 형태로 저장하여 같은 물의양을 담고있는 물병의 갯수가 짝수이면 딕셔너리를 갱신하는 형태로 하여 무식하게 구현한 실패 코드 1에 비해 좀 더 효율적이게 짜려고 했습니다.
결과적으로는 시간초과...
후기
빠르게 구현해보기 위해 알고리즘을 짜보고 그에 맞는 자료형을 이용하여 구현해 보았지만 시간초과로 2번이나 실패하여 멘붕...
결국 아이디어는 구글링을 통해 얻었지만 이번 문제를 통해서 이진법을 이용하는점이 더 좋을수도 있다는 것을 알았습니다.
무엇보다 비록 시간초과가 났지만 혼자 알고리즘을 짜고 자료형을 선택하여 짠 코드가 문제의 목적에 맞게 돌아가긴 한다는 것에 너무 뿌듯했습니다!
