[프로그래머스] 멀리 뛰기 , 귤 고르기

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

 

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/138476

프로그래머스

---

 

Think🤔

 

1. 멀리뛰기 경우의 수 다 따져봄

 

1,1,1,1,1

1,1,1,2
2,1,1,1
1,2,1,1
1,1,2,1

2,2,1
1,2,2
2,1,2

------------------
1,1,1,1,1,1 -> 1개
1,1,1,1,2 -> 5개

1,1,2,2 -> 6개
1,2,1,2
1,2,2,1
2,1,1,2
2,2,1,1
2,1,2,1

2,2,2 -> 1개

 

해보니 피보나치 수열 dp [ 동적 프로그래밍 ] 이용해서 풀어야 함

 

2. 귤 고르기

HashMap으로 받음
k = 9라 하면
제일 많이 받은 숫자부터 k에서 빼주고 0이 되면 종류 cnt해서 return

---

Solution✍

 

class Solution {
    public long solution(int n) {
        long dp[] = new long[n+2];
        dp[1] = 1;
        dp[2] = 2;
        
        for(int i=3; i<=n; i++){
            dp[i] = (dp[i-1] + dp[i-2]) % 1234567;
        }
        
        return dp[n];
    }
}

 

import java.util.HashMap;
import java.util.List;
import java.util.Collections;
import java.util.ArrayList;

class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0; // 종류
        
        HashMap<Integer, Integer> hm = new HashMap();
        
        for(int i : tangerine){
            hm.put(i, hm.getOrDefault(i, 0) + 1);
        }
        
        List<Integer> val = new ArrayList<>(hm.values());
        Collections.sort(val, Collections.reverseOrder());
        
        for(int i : val){
            if(k < 1){return answer;}
            k = k - i;
            answer++;
        }
        
        return answer;
    }
}

// HashMap으로 받음
// k = 9라 하면
// 제일 많이 받은 숫자부터 k에서 빼주고 0이 되면 종류 cnt해서 return

---

Review🤩

 

dp는 다른 사람 정답 참조 후 작성

---