개발 일지

문제 10986번: 나머지 합 (acmicpc.net) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 풀이 구간합이 M으로 나누어 떨어지려면, 슬라이딩 윈도우를 이용하되 A[i]와 A[j]의 M으로 나누었을 때 나머지가 서로 같아야 한다. 예를 들어 어떤 수 a와 b가 각각 a = 3*n + 1, b = 3*m + 2 라고 할 때, a-b = 3*(n+m) - 1로 3으로 나누어 떨어질 수 없다. a = 3*n + 1, b = 3*n + 1 이라면 가능하다. 이..

문제 12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 이미 다룬 적 있는 알고리즘이다. 0/1 Knapsack Problem - Dynamic Programming (tistory.com) 0/1 Knapsack Problem - Dynamic Programming 얼만큼의 비용과 보상이 정해진 여러개의 물체가 있다고 하자. 특정 용량까지 수용 가능한 마대에 이 물체들을 마대의 최대 수용량..

문제 채점 현황 (acmicpc.net) 채점 현황 www.acmicpc.net 풀이 두 개의 포인터 i와 j가 있을 때, ACAYKP와 CAPCAK 를 각각 A 와 B 라고 했을 때 LCS를 찾는 과정은 다음과 같을 것이다. i : 0, j : 0 이고, A[i] = 'A', B[j] = 'C' 이므로, 이제 i에 1을 더한 경우와 j에 1을 더한 경우 각각을 살펴 봐야한다. 먼저 i 에 1을 더한 경우를 살펴본다. i : 1, j : 0 이고, A[i] = 'C', B[j] = 'C' 이므로 i와 j 모두 1 씩 더한다. i : 2, j : 1 이고, A[i] = 'A', B[j] = 'A' 이므로 i와 j 모두 1 씩 더한다. i : 3, j : 2 이고, A[i] = 'Y', B[j] = 'P' ..

문제 2565번: 전깃줄 (acmicpc.net) 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 전깃줄이 어떤 상황에 교차되는지 따져보면 금방 LIS 문제라는 것을 알 수 있다. 따라서 전선을 나타내는 리스트를 만들어 가장 긴 증가하는 부분수열을 찾아주면 된다. N = int(input()) graph = [0]*501 for _ in range(N): a,b = map(int,input().split()) graph[a] = b dp = [1]*501 for i in range(1,501): for j in..

문제 11054번: 가장 긴 바이토닉 부분 수열 (acmicpc.net) 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 LIS를 각각 0번 왼쪽 -> 오른쪽으로, 오른쪽->왼쪽으로 한번씩 하면 된다. 일반적인 LIS와 마찬가지로 이진탐색을 쓸 수 있고, 두 번 해주면 되겠다. N = int(input()) A = [0] + list(map(int,input().split())) left = [1]*1001 right = [1]*1001 for i in range(1,N+1): for j in range(1,i): if A[..

문제 11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net) 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 18353번 - 병사 배치하기 (tistory.com) 18353번 - 병사 배치하기 문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다 forteqook.tistory.co..

풀이 2156번: 포도주 시식 (acmicpc.net) 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 dp[i]를 i 번째 와인을 골랐을 때 마실 수 있는 와인 양의 최대값으로 한다.3 잔 연속으로 마실 수 없다는 점에 착안하여 점화식을 세우되, i-1 번째 와인을 마시면 i-4 번째 와인을 마시는 경우와 i-3 번째 와인을 마시는 경우 두가지가 존재한다는 점을 주의하자. N = int(input()) wine = [0]*10001 for i in range(1,N+1): wine[i] = int(inp..

문제 10844번: 쉬운 계단 수 (acmicpc.net) 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 dp[i][j] 에 대해서, 길이가 i 일 때 맨 뒤 숫자가 j 일 경우 가능한 계단 수를 목표로 점화식을 작성한다. N = int(input()) dp = [[0]*101 for _ in range(N+1)] for i in range(1,10): dp[1][i] = 1 for i in range(2,N+1): for j in range(10): if j == 0: dp[i][j] = dp[i-1][j+1] elif j == 9: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = (dp[i..

문제 1463번: 1로 만들기 (acmicpc.net) 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 예를 들어 X가 6인 경우, dp[6] = min(dp[5],dp[3],dp[2]) + 1이 될 것이다. 즉 X가 2로 나눠지는 경우와 3으로 나눠지는 경우에 대해서 점화식을 세우면 된다. N = int(input()) dp = [0]*(10**6+1) dp[1],dp[2],dp[3] = 0,1,1 for i in range(4,N+1): dp[i] = dp[i-1] + 1 if i%2 == 0: dp[i] = min(dp[i], dp[i//2]+1) if i%3 == 0: dp[i] = min(dp[i], dp[i..

문제 2579번: 계단 오르기 (acmicpc.net) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 N 번째 계단을 반드시 밟으면서 계단 값들의 합이 최대가 되는 경우는, N-3번째 계단과 N-1번째 계단을 밟는 경우가 있고 N-2번째 계단만 밟는 경우가 있다. 조건에 의해 3번 연속 계단을 밟을 수 없기 때문이다. N = int(input()) stairs = [0]*10001 for i in range(1,N+1): stairs[i] = int(input()) dp = [0]*10001 dp[1] = stai..