DP24 [BOJ] 2718번: 타일 채우기 풀이 dp[i][j]를 i번째 칸, j의 상태에서 채울 수 있는 경우의 수로 놓고 풀어야 한다. 일차원 배열로 풀려고 하면 사실 경우의 수가 너무 많기 때문에 저렇게 2차원 배열을 이용하면 상대적으로 쉽게 풀 수 있다. 설명을 하기에는 너무 복잡하고 귀찮으므로 직접 찍은 영상을 통해 풀이를 하려고 한다. 코드 #include int n, T, dp[10001][16]; const int div = 100007; int main() { dp[0][15] = 1; for (int i = 1; i 2018. 5. 31. [BOJ] 1520번: 내리막 길 1520번: 내리막 길 풀이 대표적인 동적 계획법 문제라고 한다. 처음엔 어떻게 DP로 풀지??라고 생각했지만 DP라는 방향을 잡고나니 풀기 상당히 쉬워졌다. 기준값: m == 0 && n == 0일 때는 1이다. 점화식…?인지는 모르겠지만 4방향을 돌면서 본인보다 큰지 작은지 확인하면 된다. 나는 탑-다운 방식으로 해서 풀었고 visited 배열까지 써서 풀었지만 사실 dp배열을 -1로 초기화 시키고 분기문을 하나 만들어서 풀면 visited 배열을 만들 필요가 없다고 한다. 참조 코드 #include int dp[501][501], n, m; // dp[i][j]는 (0, 0)에서 (i,j)까지 가는 경우의 수 int map[501][501]; // 입력 저장하는 곳. bool visited[501].. 2018. 5. 31. [BOJ] 2133번: 타일 채우기 2133번: 타일 채우기 풀이 f(2)를 계산하고 바로 D[n]=3∗D[n−2]D[n] = 3 * D[n - 2]D[n]=3∗D[n−2]라고 생각할 수 있지만 2(D[n−4]+D[n−6]+D[n−8]+...)2(D[n - 4] + D[n - 6] + D[n - 8] + ... )2(D[n−4]+D[n−6]+D[n−8]+...)0이상까지 추가로 더해야 줘야 한다. 그 이유는 힌트 속 그림에 있다. 코드 #include int n, dp[10001] = {1, 0, 3}; int main() { scanf("%d", &n); for (int i = 4; i 2018. 5. 31. [BOJ] 2482번: 색상환 2482번: 색상환 풀이 원으로 계산하면 골치가 아파서 선형으로 만들어서 계산하고 나중에 원으로 만들어서 계산하면 된다. 조건 범위 내 모든 n에서 k=0일 땐 1이고(아무 것도 고르지 않는 것도 경우로 취급), k=1일 땐 n이다. n>1의 경우, n번째 색을 고르거나 안 고르는 두 가지 경우로 생각할 수 있는데 n번째 색을 고르면 n - 2개 중 k - 1개를 고른 것과 같고, n번째 색을 고르지 않으면 n - 1개 중 k를 고른 것과 같다. 다시 원으로 합칠 때는 양쪽 끝을 합친다고 생각하면 되기 때문에 선형의 양쪽 끝이 같은 경우를 생각해 줘야 한다. 양 끝에 색이 칠해져 있다면 이 경우는 불가능하므로 그걸 피하기 위해 양쪽 끝 중 하나를 잡아서 계산한다. 아까와 동일하게 n번째 색을 고르거나 안.. 2018. 5. 21. [BOJ] 13302번: 리조트 13302번: 리조트 풀이 dp[i][j] = j개의 쿠폰을 가지고 i일까지 있는데 드는 최소 비용. 처음에 쿠폰이 거슬렸는데 dp 배열을 2차원으로 두고 하니깐 한결 쉬워졌다. 재귀로 짰는데 for문으로도 짜보고 싶지만 잘 모르겠다. 코드 처음으로 3항 연산자의 감사함과 왜 있어야 하는가에 대해 진심으로 깨닫게 되었다... #include #include using namespace std; const int MN = 100 + 1; int N, M, dp[MN][MN / 2]; // dp[i][j]는 i일까지 j개 쿠폰 가지고 있는 최소 가격 수. bool chk[MN]; // 쉬는 날인지 확인 int f(int day, int coupon) { if (day > N) return 0; if (dp[.. 2018. 5. 20. [BOJ] 1463번: 1로 만들기 1463번: 1로 만들기 풀이 스타트링크의 최백준님께서 유튜브에 올리신 DP 강좌를 발견했습니다. 필요하신 분은 보시기 바랍니다. 링크 동적 프로그래밍으로 풀 수 있다. X를 2로 나눌 때, 3으로 나눌 때, 1를 뺄 때의 최소값을 이전 값들을 이용해 계속 업데이트를 해주면 된다 다음 그림과 같이 N = 10일 때 1이 되기 까지의 대략적인 그림을 나타낸 것이다. 문제 해결 방식으로는 2가지가 있다. 10에서 9와 5의 가지를 내릴 수 있는데 사실 이 두 개로는 결과를 도출해 낼 수 없다. 그래서 어쩔 수 없이 각각에 또 다른 뿌리를 내려서 1까지 내려가 얼마나 연산을 해야 하는지 계산할 수 밖에 없다. 이것은 재귀함수로 구현할 수 있는 방식이다.(Top-down) 또 다른 방식으로는 아래서 위로 올라가.. 2018. 5. 20. [BOJ] 2156: 포도주 시식 문제 링크설명dp[i]는 i번 것까지 먹었을 때 최댓값.현재 상태 i번째라고 했을 때 점화식 3개현재 것을 먹지 않았을 때 -> dp[i] = dp[i - 1] // i - 1 번째까지 마셨던 것을 업데이트이번 것만 먹을 때(1연속) -> dp[i] = glasses[i] + dp[i - 2] // i - 1 번은 분명히 마시지 않는다.i, i - 1번을 먹을 때(2연속) -> dp[i] = glasses[i] + glasses[i - 1] + dp[i - 3] // i - 2 번은 분명히 마시지 않는다.코드12345678910111213141516171819202122232425262728293031323334#include const int mn = 10001;inline int max(int a, .. 2018. 3. 26. [BOJ] 1003번: 피보나치 함수 1003번: 피보나치 함수풀이그래프를 그려보면 0과 1이 호출될 때 일정한 규칙이 나오는 것을 알 수 있다. 그래서 dp[i][0]은 i번째 수에서 0의 호출 횟수이고 dp[i][1]은 i번째 수에서 1의 호출 횟수이다.또는 N이 주어질 때 dp[N]은 0의 호출 횟수이고 dp[N+1]은 1의 호출 횟수가 되는데 이 이유는 잘 모르겠다... (아시는 분은 알려주시면 정말 감사드리겠습니다!)코드1번째12345678910111213#include int main(){ int n, k; scanf("%d", &n); for (int j = 0; j 2018. 3. 25. [BOJ] 1932번: 숫자삼각형 1932번 문제 풀기! 1932번: 숫자삼각형정말 고민을 많이 했는데 생각보다 간단했었따... 이게 왜 DP인지 궁금하신 분들을 위해 설명을 하자면 문제 자체가 위층에서 다음을 위해 적절한 녀석을 골라서 현재 층에서 가장 적절한 녀석을 골라 더해주는 것이다. 좀 깔끔하게 설명하지 못해서 그렇긴 한데 재귀적인 성격이 나오는 문제이다. 문제를 보면 ↘, ↙으로 갈 수 있다고 했다. 이건 위에서 아래로 내려갈 때 가정(1)이고, 아래에서 위로 간다고 가정하면 ↖, ↗으로 갈 수 있다.(2) 개인적으로 이런 문제들은 바텀-업 방식을 사용하는 것을 선호하기 때문에 (2)의 가정이 점화식을 세우기에 좋았다. [1] [2] [3] [4] [5] [1] 7 [2] 3 8 [3] 8 1 0 [4] 2 7 4 4 [5] .. 2018. 2. 3. 이전 1 2 다음
