본문 바로가기
알고리즘 문제 풀이/동적프로그래밍

백준 - 이친수(Kotlin)

by 가나무마 2022. 2. 5.
728x90

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

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

 

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

 

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

초보 알고리즘 스터디 / 누구나 참여 가능 :runner:. Contribute to ROUTINE-STUDY/Algorithm development by creating an account on GitHub.

github.com

문의는 댓글 바람.

 

문제 출처 :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으로 자료형으로 바꾸는 방법으로 처리해줬다.

 

 

728x90
반응형

'알고리즘 문제 풀이 > 동적프로그래밍' 카테고리의 다른 글

백준 - 돌 게임(Kotlin)  (0) 2022.02.23
백준 - 카드 구매하기 2(Kotlin)  (0) 2022.02.13
백준 - 계단 오르기  (0) 2022.01.29
백준 - 연속합  (0) 2021.12.23
백준 - 이름 궁합  (0) 2021.12.12