BLUE DOLPHIN

1010번: 다리 놓기 풀이 문제 읽을 때부터 뭔가 조합의 느낌이 났는데 조합이었다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 그래서 nCr을 구현해주면 된다. 코드 #include #include int n, r, D[31][31]; long long int nCr(int n, int r) { if (n == r || r == 0) return D[n][r] = 1; if (r == 1) return D[n][r] = n; if (D[n][r]) return D[n][r]; return D[n][r] = (nCr(n - 1, r - 1) + nCr(n - 1, r)); } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d %d", &n, &r); printf..

2163번: 초콜릿 자르기 풀이 감이 안 잡혔는데 그냥 우리가 실제로 초콜릿을 쪼갤 때를 생각하면 된다. 보통 반으로 계속 쪼개지 않는가? 그걸 생각하며 관계식을 세우면 된다. 가로로 반으로 쪼갤 때 or 세로로 반으로 쪼갤 때 중 최솟값을 구하면 된다. 코드 #include #include int D[301][301], N, M; int f(int n, int m) { // 종료 조건 if (n == 1) return D[n][m] = m - 1; else if (m == 1) return D[n][m] = n - 1; return D[n][m] = std::min(n * f(1, m) + (n - 1), m * f(n, 1) + (m - 1)); } int main() { scanf("%d %d", ..

5622번: 다이얼 풀이 알파벳마다 걸리는 시간을 주면 된다. 코드 #include char s[16]; int sum = 0, t[] = {3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10}; int main() { scanf("%s", &s); for (char *i = s; *i; ++i) { sum += t[*i - 'A']; } printf("%d\n", sum); return 0; }

11052번: 붕어빵 판매하기 풀이 D[i] = i개를 판매해서 얻을 수 있는 최대 이익 D[i] = D[i - k] + P[k] 중 최대값을 구하면 되는 간단한 문제다. i개 남은 거에서 k개를 선택한다면 i - k개 중 최대 이익 + k개 이익(P[k])를 더해주면 i개의 최대 이익이 되기 때문에 저런 관계식이 나오게 된다. 코드 #include #include int gN, P[1001], D[1001]; inline int Max(int a, int b) { return (a > b ? a : b); } int f(int n) { if (D[n] != -1) return D[n]; if (n == 0) return 0; for (int i = 1; i = 0) D[n] = Max(D[n], f(n..

10844번: 쉬운 계단 수 풀이 D[i][j]는 길이가 i이고 끝자리 숫자가 j인 계단 수 n=1일때의 계단 수는 1, 2, 3, 4, 5, 6, 7, 8, 9이고 n=2 일때의 계단 수는 10, 12, 21, 23, 32, 34, 43, 45, ··· 등이 있다. D[2][2]일 경우를 한 번 보자. 12, 32가 있는데 첫 자리 수는 끝자리 수인 2에서 ±1이다. 그래서 관계식이 D[i][j]=D[i−1][j+1]+D[i−1][j−1](j≠0∣j≠9)D[i][j] = D[i - 1][j + 1] + D[i - 1][j - 1](j \ne 0|j \ne 9)D[i][j]=D[i−1][j+1]+D[i−1][j−1](j≠0∣j≠9) 이렇게 나온다. j = 0일땐 D[i][j] = D[i - 1][j + ..

풀이 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

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]..

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

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∑b​i=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..

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] == ..