백준 1407 python

문제 링크

풀이방법.

어제 풀었던 문제에 이어 누적합이 재미있어서 이걸 이용해서 첫 트라이를 했다가 실패.. N과 M의 바운더리가 넓다보니 그 사이 숫자들만 어딘가에 다 넣기만 해도 부와악 하고 메모리가 드나보다..(주어진 메모리 자체도 적기는 했다.)

두 번째 시도는 첫 번째를 그냥 단순합으로 때려박은 것으로 풀고난 후 보니 만약 백준에 채점시켜본다면 시간 초과가 뜰 것 같다.

세 번째 시도는 set에 넣어서 통째로 계산해보자 하고 생각했던 것이고, 숫자 하나하나를 계산하기보다 2로 나눌때마다 홀수가 되는 숫자의 갯수를 카운트해서 result에 더해주자는 아이디어를 떠올리며 풀었다. 결론은 시간초과!... 여기서 N과 M의 조건을 다시 자세하게 보게 되었다.(문제는 항상 잘 읽을 필요가 있다.)

네 번째 시도는 세 번째에서 메모리초과가 난 이유를 생각해서 for문을 썼다가 나왔다.(결론적으로 세 번째 이하의 코드는, 물론 개선이 되긴 했지만 백준에서 시간초과와 메모리초과가 둘 다 나는 코드였다.)

마지막 통과시도는 어차피 홀수의 갯수를 카운트하는 것이니까 계산을 때려서 집어넣자라는 결론으로 대강 계산해서 집어넣은 결과이다.

'''
5 9
--> 1 2 1 8 1 ==> sum : 13
'''

# from sys import stdin

# seq = [0]
# sum_seq = [0]

# N,M = map(int,stdin.readline().strip().split())
# target = 0
# for i in range(1,M+1):
#     if i%2 == 1:
#         target = 1
#     else:
#         target = 2 * seq[i//2]
    
#     seq.append(target)
#     sum_seq.append(target+sum_seq[-1])

# print(sum_seq[M] - sum_seq[N-1])

'! 메모리 초과.'

# from sys import stdin

# sum_seq = 0

# def div_two(num):
#     cnt = 1
#     while True:
#         if num%2 != 0:
#             return cnt
        
#         cnt *= 2
#         num = num//2

# N,M = map(int,stdin.readline().strip().split())

# for i in range(N,M+1):
#     if i%2 == 1:
#         sum_seq += 1
#     else:
#         sum_seq += div_two(i)

# print(sum_seq)

'! 시도 X but 안봐도 시간이든 메모리든 초과.'

# from sys import stdin

# N,M = map(int,stdin.readline().strip().split())

# nums = {i for i in range(N,M)}
# result = 0
# tmp = 1

# while True:
#     tmp_nums = set()
#     cnt = 0
#     while len(nums) != 0:
#         x = nums.pop()
#         if x%2 == 1: # 홀수이면
#             cnt += 1
#         else:
#             tmp_nums.add(x//2)
    
#     result += tmp*cnt
#     tmp *= 2
#     if len(tmp_nums) == 0:
#         break

#     nums = tmp_nums

# print(result)

'! 이것도 메모리 초과.. 그냥 받으면 무조껀 메모리초과 나겠네..'

# from sys import stdin

# N,M = map(int,stdin.readline().strip().split())

# result = 0
# tmp = 1
# M+=1

# while True:
#     cnt = 0
#     tmp1 = (N+1)//2
#     tmp2 = (M+1)//2
#     for i in range(N,M):
#         if i%2 == 1:
#             cnt += 1
    
#     result += tmp*cnt
#     tmp *= 2
    
#     if tmp1 == tmp2:
#         break
    
#     N,M = tmp1,tmp2
    
# print(result)

'! 이건 시간초과. for문을 이용해서 푸는게 또 아니네.. cnt는 홀수의 갯수..!'

from sys import stdin

N,M = map(int,stdin.readline().strip().split())

result = 0
tmp = 1
M+=1

while True:
    cnt = M//2 - N//2
    tmp1 = (N+1)//2
    tmp2 = (M+1)//2
    
    result += tmp*cnt
    tmp *= 2
    
    if tmp1 == tmp2:
        break
    
    N,M = tmp1,tmp2
    
print(result)

'''
176 177(178) * 1
88 (89) *
44 (45) *
22 (23) *
11 (12) 16

5 6 7 8 9 (4,10) 1 * 1 * 1
  3   4   (2,5 )   2   *
      2   (1,3 )          *
      1              8

'''

cf

1. vscode에서 better comment를 사용하면 주석 뒤에 !를 찍으면 빨간색이 되는데 velog의 코드 입력창은 이를 지원하지 않아서 str(! ~~~~)로 실패한 시도의 코멘트를 달았다.

2. 코드를 짜고보니 아이디어가 간단한 듯 보여서 색다른 방법으로 포스팅하게 되었다. 이런저런 시도를 해봐야겠다.