아이테킨의 끄적끄적

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제의 조건은 세가지다. 1. 연속된 세개의 계단을 밟으면 안됨 2. 마지막 계단은 밟아야함 3. 한칸 또는 두칸씩 이동 가능함. 마지막 계단은 밟아야하므로 i번째 계단이라고 한다면 max(i-2번째 계단을 밟고 두칸을 뛰어 i번째로 온 경우, i-3번째 계단을 밟고 i-1번째를 밟고 i번째로 온 경우) 이런식으로 점화식을 만들면 된다. 코드 # 2579 - 계단 오르기 n = int(input()) step..

역시나 DP문제이므로 처음엔 점화식을 구해보려고 생각해보았다. 그러나 이전처럼 뭔가 깔끔하고 정리가 딱 되는 점화식이 생각나지 않아서 각 층마다의 최대값을 모두 구하는 방식으로 문제를 풀었다. 각 층의 첫번째 값과 마지막 값은 바로 직전 층의 값을 그대로 더해주면 되었고 그 이외의 값들은 위에 층의 더해질 수 있는 두가지 값 중 큰 값을 더해주는 방식으로 풀었다. 코드 # 1932 - 정수삼각형 # 아이디어는 각 층마다 최대값을 다 구한뒤 최대값을 찾아서 출력한다 import sys input = sys.stdin.readline n = int(input()) triangle = [] for _ in range(n): triangle.append(list(map(int,input().split()))) ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net DP문제를 계속해서 풀면서 느끼는점은 결국 점화식을 생각해내는 것이 핵심 포인트인것 같다. 문제를 어떻게 쪼개고 반복해서 연산한다음 합칠것인지 충분히 고민하고 문제를 푸는게 오히려 더 빠르고 정확하다는 생각이 든다. 점화식 i번째에 빨강을 칠할 때 최소값 = i번째 빨강의 비용 + min(i-1번째 파랑의 최소값, i-1번째 초록의 최소값) 코드 # 1149 - RGB거리 #..

이 문제도 점화식을 구하면 쉽게 풀 수 있는 문제다 그림을 유심히 살펴보거나 혹은 결과들을 유심히 살펴보면 숫자들간에 규칙이 있는것을 발견할 수 있다. (사실 다른 더 논리적이고 멋있는 해설이 있기야 하겠지만 나는 이렇게 풀었다...;;) 점화식 $$ a_n = a_{n-5} + a_{n-1} $$ 코드 # 9461번 - 파도반 수열 import sys input = sys.stdin.readline t = int(input()) for _ in range(t): dp = [0] * 101 dp[1] = 1 dp[2] = 1 dp[3] = 1 dp[4] = 2 dp[5] = 2 n = int(input()) for i in range(6,n+1): dp[i] = dp[i-5] + dp[i-1] print..

일단 이 문제는 점화식으로 표현할 수 있다면 쉽게 풀 수 있는 문제다. $$A_n = A_{n-1} + A_{n-2}$$ 처음 1,2 까지의 값만 다른 피보나치 수열이다. 점화식을 알았으니 반복문 또는 재귀함수를 이용해서 풇어주면 된다. 반복문을 이용해서 풀어보았다. # 1904번 - 01타일 # 반복문을 이용해서 - 바텀업 import sys input = sys.stdin.readline n = int(input()) tile_list = [0]*(n+1) tile_list[1] = 1 tile_list[2] = 2 for i in range(3,n+1): tile_list[i] = (tile_list[i-1] + tile_list[i-2])%15746 print(tile_list[n]) 이때 주의해..

메모이제이션을 이용해서 풀어야 하는 DP 문제다. 3차원 리스트를 이용하면 쉽게 풀 수 있다. # 9184 - 신나는 함수 실행 dp = [[[0]*21 for _ in range(21)] for __ in range(21)] def w(a, b, c) : print(dp) if a20 : return w(20, 20, 20) if dp[a][b][c]: return dp[a][b][c] if a

피보나치 함수를 구하는 문제이다 보통 피보나치 수열은 재귀함수를 이용해서 구할 수 있다. def fibo(x): if x == 1 or x == 2: return 1 else: return fibo(x-1) + fibo(x-2) 이런 식으로 구할 수 있는데 문제는 숫자가 조금만 커지게되면 연산횟수가 급격하게 증가하고 그에 따라서 속도도 엄청 느려지게 된다. 이런 문제를 메모이제이션(재귀함수이용) 또는 반복문을 이용해서 해결할 수 있다. 메모이제이션은 이미 한번 연산을 했던 값은 따로 저장해뒀다가 필요할때마다 찾아서 쓴다는 아이디어다. 말 그대로 따로 메모해둔다고 생각하면 된다. 반복문을 이용하는 방법은 작은 문제부터 하나하나씩 풀어나가는 방법이다. 결론적으로는 선형시간의 시간복잡도를 갖는다. 코드로 살펴..