BOJ1052 물병

https://www.acmicpc.net/problem/1052

 

 

1052번: 물병

 

난이도: 실버1 (난이도에 비해서는 쬐끔 어려운 듯하다.)

소요시간: 60+

 

 

 

처음접근법이 잘못되어 시간소비를 많이 하였다. 

그리고 오류를 찾느라 시간을 오래 소비하였다. 테스트 케이스를 틀리면서 찾았다. 

# 18:50 실버1
from collections import deque
import sys
N,K= map(int,sys.stdin.readline().split())

my_bottle=deque([1 for _ in range(N)])

def solve(bottle):
    new_bottle=deque([])
    while bottle:
        if len(bottle)<2:
            new_bottle.append(bottle.pop())
        else:
            bo1=bottle.popleft()
            bo2=bottle.popleft()
            if bo1==bo2:
                new_bottle.append(bo1+bo2)
            else:
                new_bottle.append(bo1)
                bottle.appendleft(bo2)

    return new_bottle

def solve2(bottle):
    while(len(bottle)>1 and (bottle[-1]==bottle[-2] or bottle[0]==bottle[1])):
        bottle=solve(bottle)
        # print(bottle)

    return bottle


my_bottle= solve2(my_bottle)
count=0
result=-1


while True:
    if len(my_bottle)<=K:
        break
    else:
        count+=my_bottle[-1]
        temp=[1 for _ in range(my_bottle[-1])]
        # print("+++")
        my_bottle+=temp
        my_bottle=solve2(my_bottle)


print(count)

 

아래는 다른 사람의 코드이다. 이진법문제가 익숙하다면 아래와 같은 접근법이 생각이 났을 것이다.

bin 메소드가 익숙하지 않아서 접근법을 알았어도 아래처럼 간결하지는 않았을 것같다. 그래도 풀이시간이 확연히 단축되었을 것 같다.

많이 풀어보는 수 밖에 없는 것같다.

# 문제 접근법이 중요하다.
# 뭔가 2진법같이 생겼다.
# 2진법으로 풀어보자

# N을 이진법으로 바꾸면 (ex, 11 => 1011)
# 물병: 1,1,1,1,1,1,1,1,1,1,1
# 합치기: 2,2,2,2,2,1
# 합치기: 4,4,2,1
# 합치기: 8,2,1
# 뭔가 규칙이 보인다.
# 결론: N을 이진법으로 바꾼 수의 1의 개수가
# 물을 최대로 합친 후의 물병의 개수이다.
N, K = map(int, input().split())

purchased_water_bottle_cnt = 0

while bin(N).count('1') > K:
    idx = bin(N)[::-1].index('1') # 1찾기, 뒤에서부터 탐색
    purchased_water_bottle_cnt += 2**idx
    N += 2**idx

print(purchased_water_bottle_cnt)