알고리즘 - Python / 백준 - 2205번 : 저울 추 만들기

2205번: 저울 추 만들기 (acmicpc.net)

2205번: 저울 추 만들기

 

---

풀이

• 질량이 1 ~ n 까지 각 무게당 한 개씩 주석과 납 덩어리가 존재한다.
• 주석과 납 덩어리들을 한개씩 적절하게 섞어 모두 2의 거듭제곱 무게가 되도록 만드는 조합을 출력하는 문제다.
• 문제에서 예외 처리가 없다는 것에서 약간의 힌트를 얻었다.
• 만약 n의 경우에 따라 모두 2의 거듭제곱 무게가 되지 못하는 경우가 있었다면 , 문제에 그러한 경우는 -1을 출력하시오 처럼 예외 처리가 있었을 것이다.
• 예외 처리가 없다는 것은 어떻게 보면 범위 내의 모든 n에 대해 문제의 조건을 만족하는 조합이 최소 1개는 있다는 것이고 그러한 답을 찾으면 된다고 생각했다.
• n이 정해지면 납과 주석을 더해 만들 수 있는 무게는 최대 2*n 이다.
• 따라서 2*n까지의 2의 거듭제곱 수들을 구해주고 , 그리디 하게 2의 거듭제곱을 만들 수 있다면 만드는 방식으로 문제를 해결하였다.
• 문제의 예시에서 또 힌트를 얻은 점은 납과 주석이 1 ~ n 으로 대칭적이라는 것이다.
• 굳이 주석 배열 , 납 배열할 것 없이 그냥 하나의 배열로 통일하여 풀었다.
• 예를 들어 n이 5인 경우에 3의 경우 5와 더해 8이 된다.
• 그러면 납 3 : 주석 : 5 고 납 : 5 주석 : 3 이므로 납 배열[3] 에 5를 넣고 이걸 보고 바로 납 배열[5] 에도 3을 넣어버리는 것이다.
• 그리디를 돌린다고 할 때 큰 수부터 그리디 하게 넣어 주어야 한다.
• 큰 수 일 수록 가능한 경우의 수가 몇 가지 없으므로 작은 수보다 빨리빨리 처리해주어야 한다.
• 예를 들어 1의 경우 n이 100이라면 100 이하의 2의 거듭제곱 수들과 모두 매칭이 가능하겠지만 ( 1 - 1 , 1 - 3 , 1 - 7 , 1 - 15 , 1 - 31 ... ) 99 같은 경우는 매칭이 가능한 경우가 매우 적다.
• 따라서 빨리 나갈 숫자들은 나가고 앞으로 가면서 쭉쭉 찾아나가면 답이 나오게 된다.

 

def ans(n):
    check = []; idx = 2
    while True:
        if idx <= (2*n)+1:
            check.append(idx)
        else:
            break
        idx *= 2
    ir = [0 for i in range(0,n+1)]; ir[0] = 1
    for i in range(len(ir)-1,0,-1):
        for k in range(0,len(check)):
            if check[k] - i <= n and check[k] > i:
                if ir[i] == 0 and ir[check[k]-i] == 0:
                    ir[i] = check[k] - i
                    ir[check[k]- i] = i
                    break
    for i in range(1,len(ir)):
        print(ir[i])

ans(int(input()))

---