의외로 알아내기 어려운 2의 거듭제곱을 더하면 나타나는 특징

1. 문제

 

27514번: 1차원 2048 (acmicpc.net)

27514번: 1차원 2048

 

2. 풀이

 

0이나 2의 거듭제곱으로 이루어진 수열이 있는데, 서로 같은 두 수를 찾으면 하나를 2배 해주고 다른 수는 0으로 바꿔준다

 

이 과정을 반복했을때, 남아있는 수열의 수 중 최댓값을 찾는 문제

 

처음에는 걍 수의 위치가 중요한 문제는 아니니.. 수열의 값 a와 그 개수를 value로 해서 dict[a] = value로 만들고

 

dict를 순회해서 value가 2개 이상 있으면 2배한 dict[2a] += 1 해주고, dict[0] += 1 해주는 식으로..

 

그러니까 수열을 counting해서 dict로 바꾼 다음, dict를 순회해서 count값이 2개 이상 있으면 2배 해줘서 새로운 key,value 만드는 식으로

 

반복문이 끝나면 dict를 순회해서 key값이 최대인게 정답이겠지

 

def simulation(A_dict):
    
    while 1:

        new = {0:0}

        find = False

        for key,value in A_dict.items():
            
            if key != 0:
                
                if value >= 2:
                
                    value -= 2
                    new[2*key] = new.get(2*key,0) + 1
                    new[0] += 1
                    find = True

                    if value > 0:
                        
                        new[key] = new.get(key,0) + value
                
                elif value == 1:
                    
                    new[key] = new.get(key,0) + value
            
            elif key == 0:
                
                new[0] += value
        
        if find:

            A_dict = new
        
        else:
            
            break
    
    answer = 0

    for key in A_dict:
        
        if answer < key:
            
            answer = key
    
    return answer


n = int(input())

A = list(map(int,input().split()))

A_dict = {}

for i in range(n):
    
    A_dict[A[i]] = A_dict.get(A[i],0) + 1

print(simulation(A_dict))

 

 

정직하게 위와 같이 해도 되기는 하지만... 관찰을 한다면 간단하게 풀 수 있다

 

2의 거듭제곱인 두 수 $a_{i}$와 $a_{j}$가 서로 같다면, 하나를 $2a_{i}$라 하고 하나를 0으로 한다는데..

 

이게 무슨 의미인가?

 

$2^{k} + 2^{k} = 2^{k} (1+1) = 2 * 2^{k} = 2^{k+1}$이더라고

 

그러니까 알고보니 두 수가 서로 같으면 그냥 더하면 되는거더라고

 

1) 특히 중요한 점은, 서로 같은 2의 거듭제곱을 더한다는 것은 그냥 2배하는 것과 같다.

 

즉 두 수를 더한 걸 수열에 추가하고 하나는 0으로 바꿔주고

 

여기에 또 하나 핵심적인 관찰은 서로 다른 두 2의 거듭제곱을 더한다면?

 

2) 만약 a < b라면, $2^{b} < 2^{a} + 2^{b} < 2^{b+1}$이 성립하더라고

 

몇개 해보면 진짜 그러더라 2 < 1 + 2 < 4, 4< 1 + 2 + 4 < 8, 8< 1 + 2 + 4 + 8 < 16, 16 < 1 + 2 + 4 + 8 + 16 < 32 .... 

 

그러므로, 두 사실을 이용해서, 2의 거듭제곱 또는 0으로 이루어진 주어진 수열의 모든 수를 전부 더한다면?

 

$a_{1} < a_{2} < ... < a_{k} < a_{k+1}$이라고 할때,

 

$$2^{a_{k+1}} <= 0 + 2^{a_{1}} + 2^{a_{2}} + .... + 2^{a_{k}} + 2^{a_{k+1}} < 2^{a_{k+1} + 1}$$이 성립한다는 사실을 알 수 있다.

 

여기서 찾고자 하는 수열의 최댓값은, $2^{a_{k+1}}$이다.

 

그러므로, 주어진 수열의 수를 전부 더한 $s = 0 + 2^{a_{1}} + ... + 2^{a_{k+1}}$을 구한다.

 

여기서 2가 밑인 로그를 취한다면...

 

$$a_{k+1} <= log2(s) < a_{k+1} + 1$$이다.

 

따라서, log2(s)에 int()함수를 취하면 $a_{k+1}$을 얻는다.

 

그러므로, $2^{log2(s)}$가 정답이 된다.

 

import math

n = int(input())

a = list(map(int,input().split()))

print(2**int(math.log2(sum(a))))

 

 

3. 문제2

 

27515번: 1차원 2048과 쿼리 (acmicpc.net)

27515번: 1차원 2048과 쿼리

 

4. 풀이

 

수열이 시작에는 빈 수열인데, 쿼리로 수를 추가하고 연산을 수행해서 최댓값을 찾고, 수를 빼고 연산을 수행해서 최댓값을 찾고 해야한다..

 

어쨌든 내가 최초로 한 counting dict로 바꿔서 푸는 방법은 적용할 수가 없더라..

 

하지만 2의 거듭제곱을 더하면 나타나는 특징을 이용한다면 쉽게 해결할 수 있다

 

여기서 중요한점은.. 처음에 s가 +2 +3 +4... 처럼 한자리만 있을테니 s[0], s[1]로만 구성되어있겠지 생각했는데..

 

생각해보니 +1024나 +2048도 들어올수 있는데 s[1]을 한다면 1024, 2048을 추가해야하는데 1,2가 추가되어서 틀리겠지

 

s[1:]를 int로 바꿔줘야겠다

 

이런 간단한것도 실수하다니... 기본을 튼튼하게 해야돼 

 

import math
from sys import stdin

q = int(stdin.readline())

a = 0

for _ in range(q):
    
    s = stdin.readline().rstrip()

    if s[0] == '+':
        
        a += int(s[1:])
    
    else:
        
        a -= int(s[1:])
    
    if a == 0:
        
        print(0)
    
    else:
        
        print(2**int(math.log2(a)))