본문 바로가기

Problem Solving/BOJ 백준

 (132)
[ 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..
[ BOJ 백준 1983번 - 숫자 박스 ] 해설 및 코드 https://www.acmicpc.net/problem/1983 목적 N개의 열, 2개의 행으로 이루어진 숫자 상자들에, 0이 아닌 수들을 순서를 지켜 배치하여, 각 열의 위 아래를 곱해 그 합의 최대값을 만들자. 접근법 1. s[i][j][k]는 1행의 i번째 수나 2행의 j번째 수가 k열에 위치했을 때의 최대값이라고 정한다. 2. 그러면 s[i][j][k]는 k열에 i번째 수와 j번째 수가 둘 다 위치하거나, 둘 중 하나만 위치하는 경우의 최대값을 취한다. 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 29 30 #include #define f(i,l,r) for(int i=l;i=r;--i) using nam..
[ BOJ 백준 1275번 - 커피숍2 ] 해설 및 코드 https://www.acmicpc.net/problem/1275 목적 N개의 정수 원소가 있는 배열에서 부분 합을 출력하고, 원소를 수정하자. 접근법 1. 세그먼트 트리 구현의 기본 예제이다.(참고, 백준 2042 - 구간 합 구하기) 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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include #define f(i,l,r) for(int i=l;i=r;--i) using namespace std; typedef long long ll; int n,q,offset; ll t[1=1)t[a]=t[a>n>>q; offset..

티스토리툴바