99클럽 코테 스터디 22일차 TIL + 오늘의 학습 키워드

☑️ 문제: 멀리 뛰기

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

프로그래머스

 

☑️ Code

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];
    }
}

풀이 발표 자료: https://docs.google.com/presentation/d/1QdToFY98jhiFAbOMPAK1S3atvIp7qDVt4sCsrDu9iqU/edit?usp=sharing

 

DP의 특징은,

1. 최적 부분 구조 (Optimal substructures): 문제에서의 최적해가 부분 문제에서도 최적해
2. 중복 부분 문제 (Overlapping subproblems): 이미 사용했던 부분 문제의 답을 다른 문제를 해결할 때도 필요한 문제

 

☑️ Kotlin으로도 풀어보기

class Solution {
    fun solution(n: Int): Long {
        val answer = LongArray(n + 1)        
        for (i in 1..n) {
            if (i <= 2) { 
                answer[i] = i.toLong()
            } else { 
                answer[i] = (answer[i - 1] + answer[i - 2]) % (1234567.toLong())
            }
        }

        return answer[n]
    }
}

 

타입을 명시해주지 않으면, i를 int로 인식해서 타입 에러가 발생한다.