sunrin
-
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
-
2193번 : 이친수알고리즘/백준(acmicpc.net) 문제풀이 2018. 5. 31. 15:16
이차원 dp로 구성한다.dp[i][2]로 구성하는데 dp[i][0]는 i자리 이친수 중 가장 뒷자리가 0인 수를, dp[i][1]는 i자리 이친수 중 가장 뒷자리가 1인 수를 의미한다. dp[i-1][0] 뒤에 0이 올 수 있고 dp[i-1][1] 뒤에도 0이 올 수 있다.dp[i-1][1] 뒤에는 0만 올 수 있다. 여기서 N이 90까지이므로 long long int로 구성한다. #include long long int dp[91][2], N; //마지막자리가 0으로 끝나는지, 1로 끝나는지 => 개수 int main() {dp[1][0] = 0;dp[1][1] = 1;dp[2][0] = 1;dp[2][1] = 0;scanf("%d", &N);for (int i = 3; i
-
2579번 : 계단 오르기알고리즘/백준(acmicpc.net) 문제풀이 2018. 5. 30. 20:03
2006년 초등부 지역본선 4번 문제입니다. 조건을 다시 되짚어보면한번에 최대 두 칸 위까지 올라갈 수 있다.연달아 3칸을 밟으면 안된다.도착 지점은 무조건 밟아야 한다. dp는 i번째 계단을 밟을때와 밟지 않을 때 각각의 최대 점수를 dp로 쌓아주시면 됩니다.즉 dp[3][1]은 3번째 칸을 밟았을 때 최대 점수이고, dp[3][0]은 3번째 칸을 밟지 않았을 때(건너 뛰었을 때)의 최대 점수입니다. 0. dp[0][0], dp[0][1], dp[1][0]은 0으로 초기화, dp[1][1]은 1번 칸 값으로 초기화.1. 해당 칸을 밟지 않았을 때는 그 전칸은 무조건 밟았다는 소리가 됩니다. 따라서 dp[i][0]은 dp[i-1][1]이 됩니다.2. 해당 칸을 밟았을 때는 dp[i-1][0]과 dp[i-..
-
1003번 : 피보나치 함수알고리즘/백준(acmicpc.net) 문제풀이 2018. 5. 30. 19:25
기본적인 DP입니다. 0에서 0의 개수는 1개, 1의 개수는 0개1에서 0의 개수는 0개, 1의 개수는 1개2는 0과 1로 쪼개지면서 0의 개수는 1개, 1의 개수는 1개3은 1과 2로 쪼개지면서 0의 개수는 1개, 1의 개수는 2개4는 2와 3으로 쪼개지면서 0의 개수는 2개, 1의 개수는 3개 즉, 4에서의 0의 개수는 2에서의 0의 개수와 3에서의 0의 개수를 더하면 되겠죠. 1도 마찬가지구요 #include int dp[100][2]; //[0] : 0, [1] : 1 int T; int f_0(int n) {if (dp[n][0]!=-1) return dp[n][0];else return dp[n][0]=f_0(n - 1) + f_0(n - 2);} int f_1(int n) {if (dp[n]..
-