PS23 [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] 2355번: 시그마 2355번: 시그마 풀이 a≤ba \le ba≤b일 때… ∑i=abi=(b−a+1)(a+b)2\sum_{i=a}^b i = \frac{(b - a + 1)(a + b)}{2}i=a∑bi=2(b−a+1)(a+b) 입력으로 int 범위 a, b가 주어지지만 분자 계산 부분에서 int 범위를 벗어나기 때문에 그것만 잘 신경 써주면 된다. 코드 #include long long swap(long long &a, long long &b) { a = a ^ b; b = a ^ b; a = a ^ b; } int main() { long long a, b; scanf("%lld %lld", &a, &b); if (a > b) swap(a, b); printf("%lld\n", (b - a + 1) * (a + b.. 2018. 5. 26. [BOJ] 2941번: 크로아티아 알파벳 2941번: 크로아티아 알파벳 풀이 순서대로 잘 묶어주기~! 코드 #include #include char s[103]; int main() { scanf("%s", s); const int size = strlen(s); int cnt = 0; for (int i = 0; i < size; ++i) { cnt++; if (s[i] == 'c' && (s[i + 1] == '=' || s[i + 1] == '-')) ++i; else if (s[i] == 'd') { if (s[i + 1] == '-') ++i; else if (s[i + 1] == 'z' && s[i + 2] == '=') i += 2; } else if ((s[i] == 'l' || s[i] == 'n') && s[i + 1] == .. 2018. 5. 26. [BOJ] 1026번: 보물 [BOJ] 1026번: 보물 풀이 한 쪽 배열은 오름차순, 다른 한 쪽은 내림차순하면 된다. 코드 #include #include #include using namespace std; int main() { int n; char A[51], B[51]; scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &A[i]); for (int i = 0; i < n; ++i) scanf("%d", &B[i]); sort(A, A + n); sort(B, B + n, greater()); unsigned int sum = 0; for (int i = 0; i < n; ++i) { sum += (A[i] * B[i]); } printf("%d\n", sum); ret.. 2018. 5. 25. [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. 이전 1 2 다음
