728x90
https://programmers.co.kr/learn/courses/30/lessons/12980
코딩테스트 연습 - 점프와 순간 이동
OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈
programmers.co.kr
처음에... 동적계획법으로 풀었다..
제한사항 숫자N 의 범위가 10억개까지 인 점을 안 보고......
메모이제이션을 위해 리스트를 할당하는데 10억개를 허용할 리가 없다....
결국 코드는 맞았는데 효율성테스트에서 전부 낙방한다
이 문제는 간단하다. 동적계획법으로 풀 필요없이
가고자하는 목적지가 2로 나눠지면 무조건 순간이동을 쓰고
2로 안나눠지면 1칸만 전진한걸로 생각하면 된다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
def solution(n):
ans = 0
x = n
while x != 0:
# 홀수일경우
if x % 2 == 1:
x = x - 1
ans += 1
# 짝수일경우
else:
x = x // 2
return ans
|
cs |
728x90
'PS > 프로그래머스' 카테고리의 다른 글
| [프로그래머스 LV 2] [1차] 프렌즈4블록 (파이썬/python) (0) | 2021.06.16 |
|---|---|
| [프로그래머스 LV 2] 캐시 (파이썬/python) (0) | 2021.06.12 |
| [프로그래머스 LV 2] 이진 변환 반복하기 (파이썬/python) (0) | 2021.06.12 |
| [프로그래머스 LV 2] 방금 그 곡 (파이썬/python) (0) | 2021.06.12 |
| [프로그래머스 LV 2] 쿼드압축 후 개수 세기 (파이썬/python) (0) | 2021.06.11 |
