![]()
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/2563 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 문제분석 소스코드 where = [[False] * 100 for _ in range(100)] N = int(input()) for _ in range(N): row,col = map(int,input().split()) for i in range(row, row+10): for j in range(col,col+10): where[i][j] = True space = 0 for i in where..
![]()
[Problem] [Solution] arr배열과 brr배열에는 A와 B가 가지고 있는 카드 숫자를 저장한다. sum_a는 A의 최종 점수를, sum_b에는 B의 최종 점수를 저장한다. num 은 A와 B가 공개한 숫자가 같은 경우가 몇 번 있었는지 세기 위한 변수이다. flag는 누가 마지막으로 이겼는지 확인하기 위한 변수이다.(flag값이 0이면 A가 flag값이 1이면 B가 마지막으로 이긴 것) 1. arr배열과 brr배열에 숫자를 입력받는다. 2. for문을 활용하여 0부터 9까지 수행한다. 2-1. arr[i]값이 brr[i]값보다 큰 경우 flag에 0을 저장하고 sum_a에 3을 더한다. 2-2. arr[i]값이 brr[i]값보다 작은 경우 flag에 1을 저장하고 sum_b에 3을 더한다...
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/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net Algorithm 같은 책을 입력 받으면 책의 개수를 +1 해주어야 하기 때문에 딕셔너리를 사용해야겠다고 생각했다. 책을 입력받으면 딕셔너리 D에 저장하는데, 처음 저장되는 경우에는 D[책이름] = 1로 만들어준다. 그 외에는 D[책이름]+=1을 해준다. 입력이 끝나면 arr라는 리스트에 딕셔너리 D의 items()값을 넣어준다. arr = [[책이름, 개수], ...] 이렇게 저장이..
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/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net [문제] [코드] [문제해설] 이 문제는 같은 숫자가 중복해서 나올 수는 있지만, 이미 나왔던 조합은 나올 수가 없게 하는 것이 관건인 문제이다. 처음에는 배열을 하나 만들어서 지금까지 생성된 조합을 모두 넣어 이미 나왔는 지 여부를 검사하는 코드를 짰었으나, 지속적으로 시간초과에 걸렸다. 시간초과를 해결하기 위해서는 이 리스트가 나왔었는 지 확인하는 것이 아닌 set을 이용해 중복을 제거하는..
