[Algorithm] 백준 1057

문제

풀이

첫번째 접근 방법 : 에 바 !

나는 원래 생각했던 알고리즘은 다음과 같다.

N을 입력 받고 배열을 만들어서 2개씩 묶어서 더하고 새로 배열에 넣고
암튼 그렇게 하려고 했었는데, 아무리 생각해도 에바였다.
그래서 어떤 규칙이 있을까 고민을 했다.

내가 생각한 알고리즘

1. N, a, b를 입력 받는다.
2. 2로 나눈 몫을 비교한다.
3. 같지 않으면, 이를 반복 수행한다.

원래는 for 문 안에 제한 범위를 2의 x승 = N 을 이용해 x 를 구하려고 했는데, 솔직히 어떤 라이브러리의 함수를 써야할지 모르겠었다.
그래서 몫을 비교한 것을 제약으로 걸어 두었다.
주의해야할 점은 처음에 1씩 빼줘야 하는 거 !

코드

n, a, b = map(int, (input().split(' ')))

a = a-1
b = b-1
cnt = 1
while int(a/2) != int(b/2):
    a = int(a/2)    
    b = int(b/2)
    cnt+=1

print(cnt)

Lesson Learn

규칙을 찾자.
단순하게 생각하자.

2의 x승 = N 일때, x의 값을 찾는 방법

import math

def find_x(N):
    x = math.log2(N)
    return x

N = float(input("N 값을 입력하세요: "))
x = find_x(N)
print("x의 값은:", x)

이 코드는 ( N ) 값을 입력 받아서 ( x ) 값을 계산하고 출력합니다. ( x ) 값은 ( 2^x = N ) 을 만족하는 값입니다.
로그 함수를 쓰면 된다.

int 형변환

n/2, int(n/2)
의 차이를 알아야 한다.
나는 솔직히 몫만 출력되어서 자연수로 될 줄 알았는데 진짜 나눈 값이 나오더라.?
그래서 몫을 사용하고자 할 때는 int 형변환을 반드시 해주도록 하자.