[파이썬/브3] 백준 31868 - 수박 게임

https://www.acmicpc.net/problem/31868

1 초

1024 MB

390

316

295

85.014%

문제

 1단계 과일은 체리, 𝑁단계 과일은 수박이다.

 𝑖단계 과일 2개를 소모하여 𝑖+1단계 과일 1개를 만들 수 있다. (1≤𝑖≤𝑁−1)

 𝐾개의 체리로 최대 몇 개의 수박을 만들 수 있는지 구해보자!

입력

첫 번째 줄에 정수 𝑁$N$과 𝐾$K$가 공백을 사이에 두고 주어진다. (2≤𝑁≤30;1≤𝐾≤10**9) 

출력

첫 번째 줄에 만들 수 있는 수박의 최대 개수를 출력한다.

예제 입력 1 복사

3 10

예제 출력 1 복사

2

 

 

---

정답

# (40ms)

n, k = map(int, input().split())
tot = k//(2**((n-1)))

print(tot)

 

풀이 과정

- 처음에는 복잡하게 풀다가 틀렸는데, 브3인데 지나치게 복잡할리가 없으니 단순하게 해보자! 라고 생각했더니 풀렸다

- 확실히 머리로만 생각할 때보다 손코딩 & 알고리즘의 흐름을 그리면서 하니 좋았다

 

1)  n, k 입력값 받기

2)  만들 수 있는 수박의 최대 개수 tot

3)  i+1단계로 넘어갈수록 (1단계 기준으로) 소모되는 과일의 개수는 2->4->8개... 로 2의 제곱수만큼 증가하는 것을 알 수 있다. (이해가 어려우면 예시 참고)

4)  이때 묶음 기준보다 작은 것들은 버리기 위해 / 대신 //를 써준다

<예제 입력1 참고>

n=5, k=20

# 수박은 5단계, 1단계인 체리는 총 20개

 

# ㅁ가 체리라고 가정

1단계 :  ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ ...  => 총 20개의 체리 => 20/1

2단계 : (ㅁ ㅁ) (ㅁ ㅁ) (ㅁ ㅁ) (ㅁ ㅁ) ... (ㅁ ㅁ) => 체리를 2개씩 묶어 10개의 작은 묶음을 만듦 => 20/2

3단계 : ( (ㅁ ㅁ) (ㅁ ㅁ))  ... ( (ㅁ ㅁ) (ㅁ ㅁ)) => 2단계의 체리묶음을 2개씩 묶어 5개의 중간 묶음을 만듦 => 20/4 = 20/(2**2)

4단계 :  [ ( (ㅁ ㅁ) (ㅁ ㅁ)) ] ... => 3단계의 묶음을 2개씩 " " 3개의 큰 묶음을 만듦 => 20/8 = 20/(2**3)

------------------------------

따라서 5단계 과일은 20//8개 만큼 만들어짐