본문 바로가기

분류 전체보기

 (146)
[ BOJ 백준 1720번 - 타일 코드 ] 해설 및 코드 https://www.acmicpc.net/problem/1720 목적 N이 주어지면, 전체 타일 코드의 개수를 구하는 프로그램을 작성하시오. (단, 서로 좌우 대칭을 이루는 중복된 표현은 한 가지 경우로만 처리한다.) 접근법 1. N이 4일 때, 좌우 대칭을 이루는 표현을 포함하여 나올 수 있는 타일 코드는 다음과 같다. 2. 타일의 모양을 살펴보면, 좌우 대칭(색칠된 타일)인 타일과 좌우가 같은 타일 두가지 경우로 나타난다. 좌우가 같은 타일은 아래 그림과 같은 타일들이다. 이와 같이 좌우 대칭인 타일을 X, 좌우가 같은 타일을 Y라고 할 때, 총 2X+Y개의 타일이 만들어 진다. 문제에서 좌우 대칭인 타일을 하나의 경우로 처리하는 것이므로 좌우 대칭인 타일을 없애야 한다. 하지만 그러한 타일을 찾기..
[ BOJ 백준 2229번 - 조 짜기 ] 해설 및 코드 https://www.acmicpc.net/problem/2229 목적 학생들의 점수가 주어졌을 때, 조가 잘 짜여진 정도의 최댓값을 구하자. 접근법 1. 예제는 다음과 같이 조를 나눠야 한다. 이 문제를 DP를 이용하여 구해내자. 2. s[i]를 i명으로 조를 짤 때의 조가 잘 짜여진 정도의 최댓값이라고 하자. 예를 들어, s[7]을 구하는 과정을 보자. 초록색 부분은 이전에 구한 값을 이용하고, 파란 부분에 있는 원소들의 최대값과 최솟값을 구해 그 차이를 초록색 부분과 더한다. s[7]은 이러한 방식으로 만들어진 아래 값들 중 최대값을 취하면 된다. 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 f(i,l..
[ BOJ 백준 1958번 - LCS 3 ] 해설 및 코드 https://www.acmicpc.net/problem/1958 목적 문자열 3개의 LCS를 구하자. 접근법 1. 백준 9252번 - LCS 2의 풀이와 비슷하다. 2차원 배열에서 3차원 배열로 DP를 적용하자. 2. s[i][j][k]를 채우는 값은 인접한 7개의 배열 요소의 영향을 받는다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include #define N 101 using namespace std; char a[N],b[N],c[N]; int s[N][N][N],i,j,k,u,v; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>a>>b>>c; for..
[ BOJ 백준 9252번 - LCS 2 ] 해설 및 코드 https://www.acmicpc.net/problem/9252 목적 입력으로 주어진 두 문자열의 LCS의 길이와 LCS를 구하자. 접근법 1. 다음과 같이 DP로 2차원 배열을 채우자. 문자열 a,b가 있을 때, s[i][j]는 a[0~i], b[0~j]까지의 lcs의 길이이다. 이러한 s[i][j]는 다음 두가지 조건으로 채운다. a[i] == b[j] 이면, s[i][j] = s[i-1][j-1] + 1 그렇지 않으면, s[i][j] = max(s[i-1][j], s[i][j-1]) 2. lcs를 구하는 과정은 s[i][j]를 채워나간 방식과 비슷하게 진행한다. 다음 그림의 ?를 s[i][j]라고 한다면 s[i][j]는 A,B,C의 영향을 받게 되며, lcs는 역방향으로 찾아 나간다. a[i] =..
[ BOJ 백준 2624번 - 동전 바꿔주기 ] 해설 및 코드 https://www.acmicpc.net/problem/2624 목적 입력으로 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수를 구하자. 접근법 1. 2개의 배열을 이용해서 i번째 동전 n개로 만들 수 있는 금액 별 경우의 수를 계속 갱신해 나간다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include #define f(i,l,r) for(int i=l;i>T>>k; s[0][0]=1; while(k--){ cin>>p>>n; f(i,0,T)if(s[0][i])f(j,1,n){ int tmp=i+j*p; if(tmp>T)break;..
[ BOJ 백준 1398번 - 동전 문제 ] 해설 및 코드 https://www.acmicpc.net/problem/1398 목적 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 과 같이 0보다 크거나 같은 모든 K에 대해서 10^K인 동전과 25*100^K인 동전들이 있다. 차를 사기위한 동전의 최소 개수를 구하자. 접근법 1. 동전 배열을 3개씩 끊어보면 100씩 곱해지는 규칙이 있다. 그리고 100단위 마다 필요한 최소 동전의 개수를 독립적으로 다른 100단위의 영향을 받지 않는다. 2. 따라서 100까지 필요한 동전의 최소 개수를 구하고, 100씩 나누어가며 결과를 계산하자. 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 f..
[ BOJ 백준 8983번 - 사냥꾼 ] 해설 및 코드 https://www.acmicpc.net/problem/8983 목적 사대의 위치와 동물들의 위치가 주어졌을 때, 잡을 수 있는 동물의 수를 구하자. 접근법 1. n마리의 동물을 주어지는 순서대로 잡을 수 있는지 여부를 검사하자. 사대를 정렬한 뒤 이분 탐색으로 시간 복잡도를 낮추도록 하자. 2. 잡을 수 있는지는 a - (L-b) 이상 a + (L-b) 이하의 범위에 사대가 존재하는지 검사하면 된다. 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>m>>n>>l; f(i,0,m)cin>>h[i]; int *end=h+m; sort(h, end); int c..
[ BOJ 백준 10090번 - Counting Inversions ] 해설 및 코드 https://www.acmicpc.net/problem/10090 목적 배열에서 inversion count를 구하자. 접근법 1. inversion count는 문제에도 나와있듯이, 역순으로 된 원소 쌍의 개수를 말한다. 다음과 같이 정렬을 하기 전과 한 후의 원소를 이어 생기는 교차점의 개수로 표현할 수 있다. 2. 합병정렬 알고리즘을 이용해 O(NlogN)의 시간복잡도로 구할 수 있다. 오른쪽에 있는 부분 배열의 원소가 왼쪽에 있는 부분 배열의 원소보다 작은 경우에 카운팅을 해주면 된다. 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 #include #define f(i,l,r)..

티스토리툴바