Menu

Subscribe

[JAVA/프로그래머스] Summer/Winter Coding(~2018) : 점프와 순간 이동

HEESOO on Programmers

👀 문제

https://programmers.co.kr/learn/courses/30/lessons/12980

👊 도전

1. 설계

  1. Top-Down 형식으로 구한다.
  2. n이 짝수면 순간이동, 홀수면 점프한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import java.util.*;
/**
 *
 * @author HEESOO
 *
 */
public class Solution {
    public int solution(int n) {
        int ans=0;
        while(n>0){
            if(n%2==0) n/=2; // 순간이동
            else{ // 점프
                n--;
                ans++;
            }
        }

        return ans;
    }
}

3. 결과

실행결과 🤟 성공 🤟
DP로 문제를 해결하였으나 효율성에서 메모리, 시간 초과가 발생했다. input이 10억 이하여서 그런 것 같다. 그래서 변수 3개를 이용하여 문제를 풀려고 했으나, 잘 되지 않았다.

4. 설명

  1. Top-Down 형식으로 구한다
    • 1에서 n까지 가는 것이 아니라, 반대로 생각한다.
    • n에서 1까지 가야하므로 while문은 n==0이 될 때까지 반복한다.
    • n이 짝수이면 순간이동하는 것이 유리하므로 n/2위치로 간다. (n=n/2)
    • 홀수라면 한 칸 앞으로 간다. (n=n-1)
    • 점프할 때만 건전지를 소모하므로 ans++한다.

👏 해결 완료!

참고