날먹 문제란 무엇인가. 깊은 생각이나 좋은 알고리즘 없이도 단순하고 간단하게, 특히 코드 길이가 짧게 풀리는 문제들을 뜻한다. 이 와중에 문제의 티어가 당연히 낮지 않아야 한다. 티어가 낮다면 그냥 쉬운 문제일테니..
딱 위 조건에 부합하는 날먹 문제들을 들고왔다. 자칭 pro 날먹 문제 풀이러로써, 실력은 없고 티어만 높다.
작성자 본인은 수학에 큰 재능이 없고, 알고리즘도 제대로 공부한 적 없어서 모른다. 하지만 티어가 괜찮은 문제들을 풀 수 있다.
날먹 1번 문제:
https://www.acmicpc.net/problem/2747
2747번: 피보나치 수
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
https://www.acmicpc.net/problem/2748
2748번: 피보나치 수 2
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
https://www.acmicpc.net/problem/10870
10870번: 피보나치 수 5
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
https://www.acmicpc.net/problem/10826
10826번: 피보나치 수 4
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
https://www.acmicpc.net/problem/15624
15624번: 피보나치 수 7
첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.
www.acmicpc.net
위 문제들을 순서대로 풀면 된다. 단 하나의 알고리즘으로 아주 쉽게 풀린다. 하지만 이 문제들을 다 풀기 위해선 피보나치 수열을 알아야하는데, 모든 문제가 풀리는 코드는 다음과 같다.
from functools import lru_cache
import sys
input=sys.stdin.readline
@lru_cache(maxsize=None)
def fib(n):
if n == 0:
return 0
elif n == 1 or n == 2:
return 1
else:
return fib(n - 1) + fib(n - 2)
n=int(input())
print(fib(n))
혹여나 피보나치 수열을 알고있지 않았는데, 답을 보고 베끼는 느낌이 들어 죄책감이 들 수도 있을 것 같다. 하지만 전혀 그럴 필요가 없는게, 어차피 언젠간 피보나치 수열에 대해 알아야 했었고, 그것은 절대로 개인이 직감적으로 떠올릴 수 있는 영역이 아니라 코드를 보면서 배워야 하는 것이다.
가까운 시일 내에 백준 날먹 문제 #2로 돌아오겠다. 이번엔 피보나치 수열 시리즈로 설명했지만, 사실 더 많은 문제들이 있다.