온라인저지 144

[BOJ] 1010번: 다리 놓기

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

온라인저지 2018.06.03

[BOJ] 2163번: 초콜릿 자르기

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", ..

온라인저지 2018.06.02

[BOJ] 11052번: 붕어빵 판매하기

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

온라인저지 2018.06.02

10844번: 쉬운 계단 수

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

온라인저지 2018.06.01

[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.05.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.05.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∑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..

온라인저지 2018.05.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.05.26