[LeetCode] Climbing Stairs

• 문제

[LeetCode]Climbing Stairs

 

알고리즘 유형중 DP(Dynamic Programming)에 관한 문제이다.

DP 관련한 문제를 접근하기 위해서는 메모제이션에 대한 이해가 필요하다. 

 

• TOP-DOWN
  위에서 아래로 접근하는 방식
  재귀를 많이 이용한다. 
• Bottom-Up 
  밑에서 위로 접근하는 방식
  for문같은 반복문을 많이 이용. 

메모제이션에 관한 이해나 부연 설명들은

아래와 같은 블로그를 참고하면 더욱더 이해하기 쉬울 것이다. 

* 김로그 

* all about coding 

 

피보나치수열처럼 점화식을 이용하면 구할 수 있는 문제였다. 

class Solution {
    fun climbStairs(n: Int): Int {
         val array = IntArray(n+1).let {
        for (i in 1..n) {
            when (i) {
                1 -> it[i] = 1
                2 -> it[i] = 2
                else -> it[i] = it[i - 1] + it[i - 2]
            }
        }
        return it[n]
    }
        
    }
}

---

• TMI 

코틀린은 also, apply, run, let, also 같은 함수들을 사용하면 좀 더 깔끔한 코드를 만들 수 있다. 

내가 작성한 코드는 n이라는 input 값을 받고 

array크기는 n+1만큼

let 함수를 써서 lamda안에 가리키고 있는 값 it은 array를 가리키고 있다고 보면 되고

반복되는 index는 1.. n까지

 

Kotlin

when(n){
  1->{
      println("$n은 1이다")
  }
  2->{
      println("$n은 2이다")
  }
  else->{
      println("$n은 3이다")
  }
}

 Java

if(n==1){
	System.out.println("n은 1이다.");
}else if(n==2){
	System.out.println("n은 2이다.");
}else {
	System.out.println("n은 1과2 가아닌 다른 값이다.");
}

   위의 코드는 코틀린과 자바 모두 같은 의미이다. 

   

이렇게 하여 내가 만든 array [n]의 위치한 값을 print 하면 문제의 답을 출력하게끔 만들었다. 

Ref)

* 문제 출처 - https://leetcode.com/problems/climbing-stairs/