Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- dfs
- Effective Java
- 그리디
- 프로그래머스
- 스택
- java
- 백준
- Network
- swea
- 이분탐색
- CS
- 구현
- BFS
- JUnit 5
- 완전탐색
- 에라토스테네스의 체
- 세그먼트 트리
- 플로이드-와샬
- 백트래킹
- Kotlin
- 유니온 파인드
- 동적계획법
- 시뮬레이션
- 후니의 쉽게 쓴 시스코 네트워킹
- 투 포인터
- 알고리즘
- 위상정렬
- mst
- 수학
- 문자열
Archives
반갑습니다!
[프로그래머스] 점프와 순간 이동 본문
풀이
처음에는 동적계획법으로 해결해야한다고 생각했지만, 조금 더 생각해보니 그리디로 해결할 수 있는 문제임을 알 수 있었다. 순간이동을 하는 경우에는 건전지를 사용하지 않기 때문에 순간이동을 최대한 많이 해야한다는 것을 쉽게 알 수 있다. N
에서부터 0으로 간다고 생각했을 때, 순간이동을 최대한 많이 하려면 현재위치가 짝수인 경우에는 2로 나눠주고, 현재 위치가 홀수인 경우에는 짝수로 만들어준다. 이 때 홀수에서 1을 빼면 짝수가 되므로 건전지 1만 사용하고도 짝수를 만들 수 있다.
코드
#include <iostream>
using namespace std;
int solution(int n) {
int ans = 0;
while(n > 0){
if(n % 2 == 0) n /= 2;
else {
n--;
ans++;
}
}
return ans;
}
'알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 17213 과일 서리 (0) | 2020.05.30 |
---|---|
[백준] 2965 캥거루 세마리 (0) | 2020.05.22 |
[백준] 3034 앵그리 창영 (0) | 2020.05.19 |
[백준] 1550 16진수 (0) | 2020.05.12 |
[백준] 15686 치킨 배달 (0) | 2020.05.12 |