본문 바로가기

분류 전체보기

 (146)
[ 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..
[ BOJ 백준 2631번 - 줄세우기 ] 해설 및 코드 https://www.acmicpc.net/problem/2631 목적 번호 순서에 맞게 줄을 다시 세울 때, 최소한의 아이들을 움직여 바로 세워보자. 접근법 1. LIS를 구한 후 N에서 빼자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include #define f(i,l,r) for(int i=l;i=r;--i) using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,c[200],ans=0,tmp; cin>>n; f(i,0,n){ cin>>tmp; int idx=upper_bound(c, c+ans, tmp)-c; if(idx==ans)c[a..

티스토리툴바