백준 26629번 백준 15841번과 매우 유사한 문제. 마찬가지로 피보나치 수열만 구현할 수 있다면 간단하게 풀어낼 수 ㅣㅇㅆ다. 내 풀이 fibo = [1,1] + [0 for _ in range(490)] for i in range(2, 491): fibo[i] = fibo[i-1] + fibo[i-2] n,*l=open(0) for i in l: if (i:=int(i)) == -1: break print(fibo[i]) CODE REVIEW 영어로 된 문제였는데, 요약하자면 피보나치 수열로 늘어나는 토끼의 수를 구하라이다. 풀이는 생략.
백준 9625번 바로가기 첫 번째 풀이 txt = "A" for _ in range(int(input())): txt = txt.replace("A","*").replace("B","BA").replace("*","B") print(txt.count("A"), txt.count("B")) 메모리 초과 에러 발생… 두 번째 풀이 a,b = 1,0 for _ in range(int(input())): a,b = b,a+b print(a,b) CODE REVIEW 역시 DP(Dynamic Programming)을 이용해야만 풀 수 있는 문제였다. 규칙을 찾아서 풀어내보자. 한 번 시행할 때마다, A -> B / B -> BA로 바뀌기 때문에 a의 갯수 -> b의 갯수 / b의 갯수 -> a+b의 갯수가 된다.
백준 9655번 바로가기 나의 풀이 game = [-1] * 1001 game[1] = 1 #SK win game[2] = 0 #CY win game[3] = 1 #SK win for i in range(4, (n:=int(input()))+1): if game[i-1] == 1 or game[i-3] == 1: game[i] = 0 else: game[i] = 1 print("SK" if game[n]==1 else "CY") CODE REVIEW 베스킨라빈스31류의 돌게임! 다만 1개 또는 3개의 돌을 꺼낼 수 있다. 그리고 마지막 돌을 꺼낸 사람이 이긴다. 점화식을 생각하면 편리하다! $a_n$번째 승자는 $a_{n-1}$번째와 $a_{n-3}$번쨰 승자와 동일하다. 따라서 game[i-1]과 game[i-3]을 확인해서 누가 이겼는지를 업데이트해주면 된다. 규칙성을 이용할 수도 있는데, 계속해서 구해나가다보면 N이 홀수면 ‘SK’ 짝수면 ‘CY’가 이기는 것을 확인할 수 있다. 다만 여기서는 DP이용하기 위해서 위 같은 논리를 이용했다.