백준 - 이친수(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/2193

 

[문제 설명]

이친수를 구하라.

 

[접근 방법]

완전탐색을 많이 풀어서 그런지 모든 문제가 완전탐색으로 보인다.

그런데 이 문제는 완전탐색으로 풀기에는 연산횟수가 무조건 초과가 나올 삘이다.

0을 붙일지 1을 붙일지 같은 단순한 알고리즘으로 하면 2^90이므로 무조건 초과다.

따라서, 규칙을 찾기로 했는데

웬걸? 써보니까 피보나치 수열이다.

1,1,2,3,5,8.... 이런 식으로 결과가 나왔다.

그래서 그냥 피보나치 구현해서 제출했다.

 

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val N = readLine().toInt()
    val arrOfPinaryNumber = LongArray(N)
    if (N <= 2) {
        println(1)
        return
    }

    arrOfPinaryNumber[0] = 1
    arrOfPinaryNumber[1] = 1
    for (idx in 0 until N-2) {
        arrOfPinaryNumber[idx+2] = arrOfPinaryNumber[idx] + arrOfPinaryNumber[idx+1]
    }

    println(arrOfPinaryNumber[N-1])
}

참고로 처음 제출은 실패했다. 피보나치 수열 90번째 항이 생각보다 엄청 커서 int로는 범위 초과가 나왔다.

단순히 Long으로 자료형으로 바꾸는 방법으로 처리해줬다.