문제 출처 : https://www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t..
분류 전체보기
문제 https://www.acmicpc.net/problem/9655 예시 코드 n = int(input()) dp = [-1] * 1001 dp[1] = 1 # SK dp[2] = 0 # CY dp[3] = 1 # SK for i in range(4, n+1): if dp[i-1] != 1 or dp[i-3] != 1: dp[i] = 1 else: dp[i] = 0 if dp[n] == 1: print("SK") else: print("CY") 풀이 상근이가 이기는 경우를 1, 창영이가 이기는 경우를 0이라고 두었다 n개의 돌이 있을 때, 맨 처음 상근이가 1개의 돌을 가져가면 남은 돌은 n-1개이고 게임의 결과는 dp[n-1]의 반대이다. (dp 내의 결과는 상근이가 시작했을 때의 결과고, 다음은 ..
n = int(input()) dp = [-1] * (n+5) dp[2] = 1 dp[3] = -1 dp[4] = 2 dp[5] = 1 for i in range(6, n+1): if dp[i-5] != -1: dp[i] = min(dp[i-2]+1, dp[i-5]+1) else: dp[i] = dp[i-2]+1 print(dp[n]) 문제 https://www.acmicpc.net/problem/14916 예시 코드 풀이 예를 들어 거스름돈이 8원일 때 동전을 최소로 내는 방법( = dp[8])은 1. 거스름돈이 6원일때 최소개수로 내는 방법( = dp[6]) + 2원 내기 => dp[6] + 1 2. 거스름돈이 2원일 때 최소개수 내는 방법( = dp[2]) + 6원 내기 => dp[2] + 1 둘 ..
https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 문제 해석 저장된 사이트 주소의 수 N 비밀번호를 찾으려는 사이트 주소의 수 M 를 입력하여 찾고 싶은 주소의 비밀번호를 출력하는 문제이다. 찾으려는 주소를 차례대로 하나씩 출력하면 된다. 코드 N, M = map(int, input().split()) c = dict() for i in range(N + M): if i < N: a, b = map(str, inpu..
문제 https://www.acmicpc.net/problem/9625 알고리즘 분류 - 다이나믹 프로그래밍 코드 K = int(input()) dp = [[0 for _ in range(2)] for _ in range(K+1)] dp[0] = [1, 0] dp[1] = [0, 1] for i in range(2, K+1): dp[i][0] = dp[i-1][0] + dp[i-2][0] dp[i][1] = dp[i-1][1] + dp[i-2][1] print(dp[K][0], dp[K][1]) 풀이 직접 써서 계산해보면 1번째: b 2번째: ba 3번째: bab => ba + b 4번째: babba => bab + ba 로 n-1번째와 n-2번째를 더한 것이 n번째임을 알 수 있다 때문에 b와 a의 개..
문제 풀이 3*N의 2차원 배열을 선언하였고, 각각의 행은 R, G, B를 나타낸다. i번째의 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다는 조건은 결국 연속한 세 집의 색이 같으면 안된다는 조건과 같다. dp[0][i] 행을 예시로 설명하면, i번째에 들어갈 최솟값은 [현재 집을 빨간색으로 칠하는 비용 + (이전 집을 초록색으로 칠하는데까지 필요한 비용, 이전 집을 파란색으로 칠하는데까지 필요한 비용, 이전 집을 빨간색으로 칠하는데까지 필요한 비용 중 최솟값)] 이다. 그런데 이전 집을 빨간색으로 칠하는데까지 필요한 비용엔 연속한 두 집을 빨간색으로 칠하는게 포함되어 연속한 세 집을 빨간색으로 칠하게 되버리니, 수정이 필요하였다. 전전 집을 빨간색으로 칠하는데까지 필요한 비용 + (이전 ..
풀이 dp배열 초기화한다. 2번 집부터 N번 집까지 순서대로 각 집을 빨강, 초록, 파랑으로 칠하는데 드는 최솟값을 계산하여 DP 배열에 저장한다. 각 집을 칠할 때, 이전 집과 색이 겹치지 않도록 하며 최솟값을 선택한다. 모든 집을 칠하는 비용의 최솟값은 DP 배열의 마지막 행에서 가장 작은 값이다. 코드 #include #include #include using namespace std; int main() { int N; cin >> N; vector cost(N, vector(3)); for (int i = 0; i > cost[i][0] >> cost[i][1] >> cost[i][2]; } vector dp(N, vector(3)); // 초기값 설정 dp[0][..
https://www.acmicpc.net/problem/13301 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net # 문제 설명 - 타일 장식물에서, {1,1,2,3,5,8...}과 같이 정사각형 타일 한 변의 길이를 구할 수 있다. - 타일의 개수 N(1 n; dp[1] = 1; dp[2] = 1; for (int i = 3; i
https://www.acmicpc.net/problem/7510 7510번: 고급 수학 준규는 집을 짓고 있다. 준규는 모든 벽 모양을 직각 삼각형으로 만들려고 한다. 적절히 나무를 잘라 삼각형을 만들었지만, 준규는 각도를 측정할 수 있는 도구를 가지고 있지 않다. 어쩔 수 없 www.acmicpc.net 문제 분석 분류 수학, 기하학, 피타고라스 정리 문제 설명 준규는 집을 짓고 있다. 준규는 모든 벽 모양을 직각 삼각형으로 만들려고 한다. 적절히 나무를 잘라 삼각형을 만들었지만, 준규는 각도를 측정할 수 있는 도구를 가지고 있지 않다. 어쩔 수 없이 줄자를 이용해 삼각형 세 변의 길이를 측정한 다음, 직각 삼각형인지 아닌지를 알아보려고 한다. 삼각형 세 변의 길이가 주어졌을 때, 직각 삼각형인지 아..
https://www.acmicpc.net/problem/2947 2947번: 나무 조각 첫째 줄에 조각에 쓰여 있는 수가 순서대로 주어진다. 숫자는 1보다 크거나 같고, 5보다 작거나 같으며, 중복되지 않는다. 처음 순서는 1, 2, 3, 4, 5가 아니다. www.acmicpc.net 문제 분석 분류 구현, 시뮬레이션 문제 설명 동혁이는 나무 조각을 5개 가지고 있다. 나무 조각에는 1부터 5까지 숫자 중 하나가 쓰여져 있다. 또, 모든 숫자는 다섯 조각 중 하나에만 쓰여 있다. 동혁이는 나무 조각을 다음과 같은 과정을 거쳐서 1, 2, 3, 4, 5 순서로 만들려고 한다. 첫 번째 조각의 수가 두 번째 수보다 크다면, 둘의 위치를 서로 바꾼다. 두 번째 조각의 수가 세 번째 수보다 크다면, 둘의 위..
문제 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 문제 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄..
https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 문제 분석 난이도 골드 3 분류 LCS, DP 들어가기 전에 앞서 LCS 문제들을 풀고오지 않았다면 더 어려울 수 있다. 문제 문제 풀이 풀이 기존 LCS코드에(2중 for문)에 한 줄을 더 늘려주면 된다. 그렇게 되면 3개가 같을 경우 +1이 되므로 사실 2개일 때랑 별 차이가 없는 문제이다. (4개라면 4중, 5개라면 5중으로 굴려주면 될 것이다. 시간복잡도가 N^5인 것만 감안하면..!) 소스코드 def ..
