[백준/Python] 1094번 : 막대기

 

 

 

이 문제는 알고보면 쉬운 문제지만, 문제의 설명 자체가 너무 부실하고 이상해서 애를 먹었던 문제다...

문제 설명만 보면 골드가 아깝지 않을 정도로 전혀 이해가 되지 않아 나와 같은 처지의 사람들이 모인 질문 게시판의 답변을 들락거리면서 간신히 이해했다.

(백준 자체에 좀 설명이 이상한 문제들이 꽤 있는 듯 함...)

 

 

내가 작성해본 예시로 간단히 설명해보겠다.

 

만약 X = 10을 입력한 경우, 합계와 자른 막대기들의 구성이 다음과 같은 과정으로 변하게 됨

64        sum: 64  lst: [64]
-> 32     sum: 32  lst: [32]
-> 16     sum: 16  lst: [16]
-> 8 / 8  sum: 16  lst: [8, 8]
-> 8 / 4  sum: 16  lst: [8, 4]
-> 8 / 2  sum: 16  lst: [8, 2]

 

- 초기 길이 64cm인 막대를 갖고 있으니 리스트에는 64만 있고, 이를 반으로 잘랐을 때 32 또한 합계가 X(10)보다 크기 때문에 64는 사라지고 이 자리를 절반인 32만 들어가게 된다.

이때 처음엔 리스트에 큰 막대 길이부터 순서대로 쌓이니까 제일 짧은 막대를 갖고 오기 위해 lst[-1]을 사용하고 64를 삭제하기 위해 del을 써서 삭제했었는데, 이렇게 하니까 코드가 지저분해져서 그냥 두 과정을 pop() 하나로 대체함

 

- 그 다음 16을 쪼개 8cm가 되는 경우 8이 X(10)보다 작으므로 하나를 버릴 수 없기에 8, 8 두 개가 모두 리스트에 들어감

- 이후의 과정도 같이 반복되어 8과 2만 남아 X=10인 경우 2 조각을 합치면 되는 것을 볼 수 있다.

 

 

따라서 한 문장으로 요약하자면, 막대의 길이를 절반으로 자르면서 원하는 길이 Xcm에 도달할 수 있도록 하는 것!

 

X = int(input())

# 초기 막대 설정
rods = [64]

# 막대 길이의 합이 X보다 큰 동안 반복
while sum(rods) > X:
    # 가장 짧은 막대 절반으로 자르기
    rod = rods.pop() // 2
    rods.append(rod)
    
    # 절반 중 하나를 버릴 수 있는지 확인
    if sum(rods) >= X:
        continue
    else:
        rods.append(rod)

# 남아있는 막대의 개수 출력
print(len(rods))

 

1. 초기 막대 길이가 64이므로, 풀이 단계에서 막대 길이들을 저장할 리스트를 생성하여 초깃값으로 64를 저장

2. 현재 막대 길이의 합이 X보다 클 동안 반복

- 가장 짧은 막대를 절반으로 자름 => rods.pop()//2

- 그리고 이것을 하나 먼저 리스트에 넣어놓고, 이 원소를 포함한 리스트의 합계가 X보다 클 경우 하나를 버림

3. 최종적으로 리스트에 남게되는 막대들은 모두 Xcm 막대기를 구성하는 데에 모두 사용되는 막대들만 남아있으므로 len()을 사용하여 개수를 출력한다.