![]()
1. 문제 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 해결 사실 해결 방법은 단순했다. - DP를 사용해자. - [ 알고리즘 ] 다이나믹 프로그래밍(DP) - 개념 - 문제에서 '구하라는 값'에 집중하자 → 나머지 값을 메모이제이션에 넣어보자 ~ 3. 코드 n = int(input()) dp= [0,1,1] for i in range(3,n+1): dp.append((dp[i-1]+dp[i-2])%1000000007) print(dp[n])
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net [알고리즘] 이 문제는 주어지는 리스트 크기만큼 dp를 먼저 선언해두고 계속해서 값을 갱신해주는 방식이다. 배열 원소들의 크기를 비교한 뒤, 바로 count를 해주면 되지않나?라고 생각을 했는데 "수열의 길이"를 구하라고 했기 때문에 dp[i]에 계속 누적을 해줘야 하고 누적된 값들 중, 최댓값을 찾아야 하므로 dp[i..
![]()
https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 접근방식 DP - 다이나믹 프로그래밍 (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있다는 것은 오른쪽, 아래쪽, 대각선으로 갈 수 있다는 것이다. dp를 사용해 이전 방에서 다음 방으로 이동 했을 때 이전 방의 최대값을 다음 방의 값과 합해야 한다. 즉, 이동할 방이 (r,c) 라면 (r-1,c) (r,c-1), (r-1,c-1) 값 중 최대값을 더한다 imp..
![]()
https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 상근이부터 시작할 때 돌이 1개, 3개, 4개 있을 때는 무조건 상근이가 승리할 수 있다. 돌이 2개일 때는 상근이는 1개 밖에 가져갈 수 밖에 없기 때문에 창영이가 승리한다. 돌이 5개 이상일 때는 한 번에 게임을 끝낼 수 없기 때문에 상근이가 1개 혹은 3개 혹은 4개를 가져갔을 때 남은 돌의 갯수에 따라 승리하는 사람을 구해보면 된다. import sys def main(): n = int(sys.stdin.readline()) game = ["SK","CY","SK","SK"] if n>4: for i in..
https://www.acmicpc.net/problem/9251 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 처음에 시간제한이 0.1초길래 완탐으로는 못풀겠구나 했는데 역시 틀림 그래서 얌전히 DP로 해결했습니다 점화식을 떠올리기 힘들었는데, 한 블로거의 잘 정리된 글을 읽고 이차원배열을 이용해서 해결함..
![]()
문제코드 #include using namespace std; int dp[1001]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; dp[1] = 1; dp[2] = 2; for (int i = 3; i
![]()
16395번: 파스칼의 삼각형 (acmicpc.net) 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net 소스코드 코드설명 n번째 행의 k번째 수를 찾기위해 n,k 입력 받음 n이 1 또는 2이면 행에 1만 존재하기 때문에 k의 값과 없이 1 출력 n이 3 이상일 때 2행 [1,1]인 dp 생성, dp를 copy한 dp2 생성 3행부터 생성하므로 3 = n 범위 내에서 반복 dp2는 새로 생성한 행, dp는 새로운 행을 생성하기 위해 이용하는 행이므로 dp를 dp2로 업데이트 fun(i) 함수를 이용..
https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 문제 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 크기 n이 ..
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net public class s_1931 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int ans = 0; int[][] arr = new int[n][2]; for (int i = 0; i < n; i++) { StringTokenizer st =..
정답 풀이 import sys from collections import deque N, Q = map(int, sys.stdin.readline().split()) # make weighted graph G = {n:deque() for n in range(1, N+1)} for _ in range(N - 1): p, q, v = map(int, sys.stdin.readline().split()) G[p].append((q,v)) G[q].append((p,v)) for _ in range(Q): ki, vi = map(int,sys.stdin.readline().split()) visited, queue, ans = [0]*(N+1), deque(), 0 # BFS visited[vi] = 1 fo..
문제 https://www.acmicpc.net/problem/1895 1895번: 필터 숫자 9개가 오름차순이나 내림차순으로 정렬되어 있을 때, 중앙값은 다섯 번째 숫자이다. 예를 들어, 1, 3, 4, 1, 2, 6, 8, 4, 10의 중앙값은 4이다. (1 ≤ 1 ≤ 2 ≤ 3 ≤ 4 ≤ 4 ≤ 6 ≤ 8 ≤ 10) 이미지 I는 www.acmicpc.net Algorithm 2차원 배열 A와 3x3 크기의 필터 K에 대해 B의 좌측 상단 부분을 A의 좌측 상단에 맞추고 필터 K를 오른쪽으로 한 칸씩 옮기고 오른쪽으로 더이상 옮길 수 없을 때는 아래로 한 칸 옮기고 아래로도 움직일 수 없을 때까지 같은 과정을 반복한다. 이 과정을 반복하는 동안 K와 A가 겹치는 영역에 해당하는 원소들로 이루어진 li..
https://www.acmicpc.net/problem/13423 13423번: Three Dots 직선 위에 서로 다른 N개의 점이 찍혀 있다. 점 i의 위치는 Xi이다. N개의 점 중 3개를 골라 가장 왼쪽에 있는 점을 a, 가운데 있는 점을 b, 가장 오른쪽에 있는 점을 c라고 하자. 각각의 점의 위치는 www.acmicpc.net RESULT """pypy3""" from collections import defaultdict import sys input = sys.stdin.readline for _ in range(int(input())): n = int(input()) li = sorted(list(map(int, input().split()))) ans = 0 dd = defaultdi..
