[ TIL - PGS ] 99클럽 코테 스터디 23일차 TIL + 오늘의 학습 가이드

💡 오늘의 학습 키워드

• 동적계획법

 

✅ 오늘 공부한 내용

• 오늘의 프로그래머스 문제! 멀리 뛰기

프로그래머스

 

👀 오늘의 회고

🤣 오늘의 문제점

• 규칙을 찾는게 제일 어려웠다!

 

🔥 어떤 시도를 했는가?

• 초반엔 조합으로 한 자리씩 계산하려고 했는데 테스트 1번만 통과하는 사태가 발생했다.
• 그 뒤로 한 칸씩 뒤로 규칙을 찾기 시작했다.

	// 1 - 1, 2 - 2, 3 - 3, 4 - 5, 5 - 8
        
        // 1 2 3 4 5
        
        // 1 
        
        //   2
        // 1 1
        
        // 1 1 1
        // 2   1
        // 1   2
        
        // 1 1 1 1  
        // 2 1 1 
        // 1 2 1
        // 1 1 2 
        //   2   2
        
        // 1 1 1 1 1    
        // 2 1 2
        // 1 2 2
        // 1 1 1 2
        // 1 2 1 1 
        // 2 2 1  
        // 1 1 2 1
        // 2 1 1 1

 

• 그래서 조합의 규칙을 찾아보니 5칸을 가려면 4칸의 경우의 수와 3칸의 경우의 수를 더한 값이 5칸의 경우의 수가 되는 것을 알 수 있다.
• DP를 활용해서 배열을 활용하여 메모리를 줄일 수 있다!

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

 

👏 무엇을 새로 알았는가?

• DP에 대한 다양한 방법들에 대해 알게 된 것 같다.

 

👩‍💻 내일은 무엇을 학습할 것인가?

• 항해 99 문제 풀기
• 문제 풀기