예상 대진표
https://school.programmers.co.kr/learn/courses/30/lessons/12985
문제 설명
_△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, … , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.
이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다._
제한 조건
- N : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
- A, B : N 이하인 자연수 (단, A ≠ B 입니다.)
입출력 예
| N | A | B | answer |
|---|---|---|---|
| N | A | B | answer |
| 8 | 4 | 7 | 3 |
입출력 예 설명
첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.
풀이
def solution(n,a,b):
# n : 총 참가인원
# a : A의 참가번호
# b : B의 참가번호
answer=0
while a != b:
a = (a+1)//2
b = (b+1)//2
answer+=1
return answer
# 이전에 푼 코드
def solution(n,a,b):
while a!=b:
a = (a+1)//2
b = (b+1)//2
answer+=1
return answer
다른 풀이
# 1. bit_length()
def solution(n,a,b):
return ((a-1)^(b-1)).bit_length()
#2 -> while True
def solution(n,a,b):
cnt=0
while True:
a= (a//2)+(a%2)
b= (b//2)+(b%2)
cnt+=1
if a==b:
break
return cnt
점프와 순간 이동
https://school.programmers.co.kr/learn/courses/30/lessons/12980
문제 설명
_OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.
예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다. 아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.
- 처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다.
- 처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다.
- 처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.
위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다. _
제한 조건
- 숫자 N: 1 이상 10억 이하의 자연수
- 숫자 K: 1 이상의 자연수
입출력 예
| N | return |
|---|---|
| 5 | 2 |
| 6 | 2 |
| 5000 | 5 |
풀이
def solution(n):
ans = 0
#5 >> 1 (+1) > 2(x) > 4(x) > 5(+1) = 2
#5 >> 5-1(+1) > 4/2(x) > 2/2(x) > 1-1(+1) = 0
while n!=0:
if n%2 == 0: #짝수이면
n = n//2
else: #홀수이면
n = n-1
ans+=1
return ans
다른 풀이
def solution(n):
return bin(n).count('1') # 2진수로 변환해서, 1의 갯수를 카운팅...
멀리 뛰기
https://school.programmers.co.kr/learn/courses/30/lessons/12914
문제 설명
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.
제한 조건
- n은 1 이상, 2000 이하인 정수입니다.
입출력 예
| s | return |
|---|---|
| 4 | 5 |
| 3 | 3 |
풀이
def solution(n):
answer = 0
num_1=1
num_2=2
if n <= 3:
answer=n
else:
for _ in range(3,n+1): #n이 3이상일 때 3이면 1회 for, 4면 2회 loop
answer = num_1 + num_2
num_1 = num_2
num_2 = answer
return answer % 1234567
다른 풀이
# 점화식을 리스트 형태로 표현
def solution(n):
if n < 3:
return n
else:
d = [0] * (n+1)
d[1], d[2] = 1, 2
for i in range(3, n+1):
d[i] = d[i-1]+d[i-2]
return d[n] % 1234567
💡 같은 코드이나 한줄로 표현 가능
for _ in range(3,n+1):
answer = num_1 + num_2
num_1 = num_2
num_2 = answer
# 같은 코드이나 한줄로 표현 가능
for _ in range(3,n+1):
num_1, num_2 = num_2, num_1+num_2 ### 한줄로 가능