알고리즘/백준(acmicpc.net) 문제풀이
-
2294번 : 동전2알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 7. 00:53
문제를 보면 숨이 막힙니다. 어떻게 풀지 감도 안오는 경우가 많죠. 생각을 조금 다르게 하면 오히려 쉬운 문제가 될 수 있습니다.동전의 가치에 초점을 두지 않고, 동전의 개수와 가치의 합에 초점을 두는 것이죠.우선 변수들의 범위부터 파악을 해봅시다.동전의 가치는 총 100개까지 입력받을 수 있습니다.동전의 가치는 100000보다 작거나 같은 수 입니다.가치의 합은 최대 1부터 10000까지입니다. 그러면 이제 dp테이블을 설계해봅시다.dp[i]가 무엇을 뜻해야 값이 쌓일 수 있을까요? 굳이 dp[i-1]과 dp[i]가 관련될 필요는 없습니다.네. 많은 풀이가 있겠지만 저는 dp[i]=가치의 합이 i원이 될 때의 최소 동전 개수 로 정의하였습니다.이때 가치의 합은 최대 100000이 될 수 있으니 dp[1..
-
2167번 : 2차원 배열의 합알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 6. 15:47
부분사각형을 구하는 문제다. 이 문제의 핵심은 "사각형을 어떻게 만들 것인가"이다. 위 사각형을 보자. 왼쪽 아래 꼭지점이 원점이라고 할 때, 1번 사각형의 넓이는 어떻게 나타낼 수 있을까?그렇다. (전체 사각형의 넓이)에서 (2번사각형+4번사각형)을 빼고 (3번사각형 + 4번사각형)을 뺀 다음 (4번사각형)을 더해주면 된다.왜 이런 방법을 쓸까?그 이유는 넓이를 표현하기가 쉬워서 그렇다. 이 그림을 보면 ((0,0)은 4번사각형의 왼쪽 아래 꼭짓점을 나타냄) 1) (전체 사각형의 넓이)는 (0,0) 에서 (x,y)까지의 넓이2) (2번사각형 + 4번사각형)은 (0,0)에서 (i, y)까지의 넓이3) (3번사각형 + 4번사각형)은 (0,0)에서 (x, j)까지의 넓이4) (4번사각형)은 (0.0) 에서 ..
-
9465번 : 스티커알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 6. 14:18
까다롭게 보이지만, 실제로는 전혀 까다롭지 않다.행은 2행으로 고정되어있고 열이 유동적이니 1열부터 n열까지 dp를 채워나가면 될 것 같다.각 열마나 선택지가 총 3개가 있다. 아무것도 선택하지 않거나, 1행을 선택하거나 2행을 선택하는 것이다. i번째 열에서 아무것도 선택하지 않을 때 dp에는 dp[i][0]으로 들어간다.1행을 선택하면 dp[i][1], 2행을 선택하면 dp[i][2]로 들어간다. 편의상 MAX(a, b)는 a와 b중 더 큰값을 반환하고, MAX3(a, b, c)는 a, b, c 중 제일 큰값을 반환한다.1) 아무것도 선택하지 않을 때 그 이전 열까지 합이 최대가 되는 dp의 값을 그대로 갖는다.ex)dp[3][0]=MAX3(dp[2][0], dp[2][1]. dp[2][2])가 된다..
-
2163번 : 초콜릿 자르기알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 5. 08:43
아주 쉬운 dp로 구성할 수 있다.입력받은 N과 M중 하나(N)를 고정시켜놓고 다른 하나를 1부터 M까지 증가시키면 된다.dp[1]은 Nx1의 초콜릿을 자르는 횟수인 N-1을,dp[2]는 Nx2의 초콜릿을 자르는 횟수인 dp[1]+N - 1 + 1(가로로 한번 추가)이렇게 증가시켜 나가면 된다. #include int N, M, dp[301];int main() {scanf("%d %d", &N, &M);dp[1] = N-1;for (int i = 2; i
-
1010번 : 다리 놓기알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 5. 01:04
처음에는 고3 확통때 배우는 조합 식인 을 이용하려 했으나 계산 과정에서 long long int 자료형도 담아낼 수 없는 값이 나와서 어쩔수 없이 조합 식을 dp에 적용하였습니다.dp[i]는 i개 중 N개를 고를 때의 경우의 수입니다. N이 3일때,dp[6]은 이고,dp[7]은 입니다. dp가 6에서 7로 변할때 4를 나누고 7을 곱한 것 처럼 dp가 i-1에서 i로 변할 때는 dp[i]=dp[i-1] * i / (i-N)가 됩니다.따라서 각 케이스마다 dp[M]까지 테이블을 채우면 쉽게 답이 나옵니다. 이 경우에는 값이 int 자료형에 충분히 들어갑니다. #include int dp[31];int main() {int T;scanf("%d", &T);while (T--) {int N, M;scanf(..
-
2156번 : 포도주 시식알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 4. 17:31
약간 복잡한 dp테이블을 세워야 하지만 2579번 계단 오르기와 많이 비슷하다.dp를 세울 때 i번째에 자신이 포함될 때와 포함되지 않을 때 두가지의 경우를 생각해 주면 된다. 왜냐하면 i+1, i+2에서 i번째를 포함 할지 안할지 모르기 때문이다.dp[i][j]는 i번째에 j가 0이면 i번째를 포함하지 않는 것, 1이면 i번째를 포함하는것을 의미한다.그렇다면 어떻게 해야할까? 우선 dp[1][0]과 dp[1][1]은 각각 0과 arr[1]로 초기화한다.i번째에 자신이 포함되지 않을 때는 dp[i-1][0]과 dp[i-1][1]을 비교(i-1번째 수를 포함시키는 경우와 포함시키지 않는 경우를 비교)해서 더 큰값을 이용한다.i번째에 자신을 포함할 때는 조금 복잡해진다. 연속해서 3번을 뽑을 수 없으니 이 ..
-
1932번 : 정수 삼각형알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 4. 14:38
dp로 해결했습니다. 레벨을 i라고 할 때 그 전레벨인 i-1레벨에서 각각의 정수 j (i-1레벨에 대한 j는 총 i-1개만큼 있습니다)에 대한 dp를 해당 칸을 포함한 정수의 합의 최댓값으로 설정합니다. 즉 dp[i][j]는 그 전 레벨의 인접한 두 노드중 더 큰 값을 선택합니다.여기서 arr[i][j]의 그 전레벨에 인접한 두 노드는 arr[i-1][j-1] 와 arr[i-1][j]입니다. ex)arr[3][2]의 그 전레벨에 인접한 두 노드는 arr[2][1]와 arr[2][2]가 됩니다.하지만 여기서 한가지 생각해보아야 할 것은 arr[2][2]의 전레벨에 인접한 두 노드는 arr[1][1]과 arr[1][2]가 되어야 하는데 arr[1][2]에는 값이 없습니다. 이것은 초기화를 모두 삼각형에 들..
-
11726번 : 2 x n 타일링알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 4. 13:02
간단한 dp로 풀 수 있다. 2 x i 타일은 2 x (i-2) 타일에 가로타일 2개를 붙인것과 2 x (i-1)타일에 세로타일 1개를 붙인 것을 더한 것과 같다.따라서 dp식은 dp[i]=dp[i-1]+dp[i-2]이다. 여기서 dp는 10007로 나눈 값을 저장해야하므로 더하는 식에 %10007을 추가해준다. #include #define R 10007int dp[1000],N;int main() {dp[0] = 1;dp[1] = 1;scanf("%d", &N);for (int i = 2; i
-
1149번 : RGB거리알고리즘/백준(acmicpc.net) 문제풀이 2018. 6. 1. 00:43
정말 간단한 dp문제이다. 제시된 조건은1. 모든 집들은 일직선상에 나란히 있다고 생각.2. 모든 집에 빨강, 초록, 파랑 중 한가지 색깔로 집을 칠해야함.3. 이웃한 집에는 같은 색으로 칠할 수 없음.4. 비용의 최솟값을 구하여라. dp[i][3]으로 구성한다. ex) i번째를 빨강으로 칠하는 최소 비용 = dp[i][0]i번째 집을 특정 색상 c1로 칠하려면 i-1번째 집은 색상 c2 또는 c3로 칠해져 있어야 한다.최솟값을 구하려면 dp[i-1][c2]와 dp[i-1][c3] 중 더 적은 값에 현재 c1의 비용을 더해주면 dp[i][c1]이 완성된다.같은 방법으로 c2로 칠할때와 c3로 칠해줄 때를 모두 구해주면 된다. #include int dp[1001][3], N; int MIN(int a, ..
-
117272번 : 2xn 타일링 2알고리즘/백준(acmicpc.net) 문제풀이 2018. 5. 31. 15:19
dp로 구성한다.dp[i]는 2xi 직사각형을 2x1과 2x2 타일로 채우는 방법의 수이다. 1) i가 하나 늘어나면 세로로 된 2x1타일 하나밖에 올 수 없다.2) i가 두 개 늘어나면 가로로 된 2x1타일 2개가 오는 경우와 2x2타일 1개가 오는 경우를 생각할 수 있다.여기서 세로로 된 2x1타일 2개가 오는 경우는 이미 1)에서 확인 했으므로 배제한다. #include #define R 10007int dp[1001], N;int main() {scanf("%d", &N);dp[0] = 1;dp[1] = 1;for (int i = 2; i