본문 바로가기

Problem Solving

 (135)
[ Codeforces 1296A - Array with Odd Sum ] 해설 및 코드 https://codeforces.com/contest/1296/problem/A Problem - A - Codeforces codeforces.com 목적 필요하다면 i번째 원소를 j번째 원소로 대체하여, 배열의 원소를 모두 더한 수가 홀수가 될 수 있는지 판별하자. 접근법 1. 배열에서 짝수와 홀수원소의 개수를 구한 뒤, odd sum이 가능한 조건을 검사한다. 2. 짝수의 개수가 0인 경우에 홀수의 개수는 홀수개여야 하고, 짝수의 개수가 1이상인 경우에 홀수가 하나라도 존재해야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #define f(i,l,r) for(int i=l;i> t; while (t--) { int n; c..
[ BOJ 백준 2602번 - 돌다리 건너기 ] 해설 및 코드 https://www.acmicpc.net/problem/2602 목적 두루마리의 문자열이 "RGS"라면 아래와 같은 돌다리는 다음 세가지 방법으로 건널 수 있다. 이러한 경우의 수를 구하자. 접근법 1. s[i][j][k]는 돌다리의 i번째 행, j번째 열이 두루마리의 k번째 문자와 같을 때의 가능한 경우의 수이다. 2. 메모이제이션을 이용하여 슥삭! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #define f(i,l,r) for(int i=l;i> key >> stone[0] >> stone[1]; cout
[ BOJ 백준 2056번 - 작업 ] 해설 및 코드 https://www.acmicpc.net/problem/2056 목적 선행 관계가 있는 모든 작업을 완료하기 위해 필요한 최소 시간을 구하자. 접근법 1. "K번 작업에 대해 선행 관계에 있는 작업들의 번호는 모두 1 이상 (K-1) 이하이다." 라는 조건으로 그래프든 위상정렬이든 다 필요 없다. n크기의 배열만 앞에서부터 차곡차곡 채워나가자. 2. a[i]는 i번째 작업의 완료시간으로, 선행 작업들의 완료시간 중 최대값과 i번째 작업의 소요시간을 더한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #define N 10001 #define f(i,l,r) for(int i=l;i> n; f(i, 1, n) { cin..
[ BOJ 백준 1520번 - 내리막 길 ] 해설 및 코드 https://www.acmicpc.net/problem/1520 목적 지도가 주어질 때 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하자. 접근법 1. 메모이제이션 기법을 이용하여 상하좌우 인접한 지점의 경우의 수를 계산하자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #define f(i,l,r) for(int i=l;i= a[i][j])continue; ref += sol(ni, nj); } return ref; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ..
[ BOJ 백준 17070번 - 파이프 옮기기1 ] 해설 및 코드 https://www.acmicpc.net/problem/17070 목적 아래와 같이 밀어 파이프 끝을 (N,N)에 위치 시킬 수 있는 경우의 수를 구하자. 접근법 1. s[i][j][k]를 파이프의 방향이 k이고 끝이 (i, j)에 있을 때의 경우의 수로 정한다. 2. 방향에 따라 밀 수 있는 경우를 모두 검사하여 계산한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include #define f(i,l,r) for(int i=l;i
[ BOJ 백준 12865번 - 평범한 배낭 ] 해설 및 코드 https://www.acmicpc.net/problem/12865 목적 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구하자. 접근법 1. s[i][j]는 i개의 물건들을, 최대 j의 무게까지 담을 수 있는 가방에 담을 때의 최대 가치로 정한다. 다음과 같은 입력으로 보자. 1 2 3 4 5 6 7 6 9 3 6 2 7 4 6 4 2 4 10 1 5 총 6개의 물건이 있고 가방에 담을 수 있는 최대 무게는 9이다. 먼저 무게가 3이고 가치가 6인 첫 번째 물건으로 s값을 갱신하면 다음과 같이 될 것이다. 다음 무게가 2이고 가치가 7인 두 번째 물건으로 s값을 갱신해보자. s[2][7]을 보면 s[2][7 - 2] + 7 과 s[1][7]중에 최대값으로 값을 채워 넣은 것을 알 수 있다. 즉, s[i]..
[ BOJ 백준 5582번 - 공통 부분 문자열 ] 해설 및 코드 https://www.acmicpc.net/problem/5582 목적 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 구하자. 부분 문자열은 연속해야 한다. 접근법 1. 두 문자열 a,b가 입력으로 주어진다면, s[i][j]는 a문자열의 i번째와 b문자열의 j번째의 공통 부분 문자열의 길이이다. 2. 따라서, s[i][j]는 a[i]와 b[j]가 같다면 s[i-1][j-1] + 1이고, 아니라면 0으로 값을 채워나간다. 그리고 최대 값을 갱신한다. 3. 이 문제에서 답을 담을 배열은 4000*4000까지의 공간이 필요 없으므로 2*4000으로 선언하여 사용한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..
[ BOJ 백준 9251번 - LCS ] 해설 및 코드 https://www.acmicpc.net/problem/9251 목적 최장 공통 부분 수열(LCS)를 구하자. ACAYKP와 CAPCAK의 LCS는 ACAK이다. 접근법 1. 문자열 a와 b가 입력으로 주어질 때, s[i][j]는 a문자열의 i번째, b문자열의 j번째까지의 LCS라고 가정한다. 2. 그러면 s[i][j]는 다음 세 가지 결과 값의 최대값이다. s[i][j-1], s[i-1][j], s[i-1][j-1]+(a[i]==b[j]) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include #define f(i,l,r) for(int i=l;i> a >> b; s[0][0] = (a[0] == b[0]); f(j, 1, b.length())s[0][j] = (a..

티스토리툴바