본문 바로가기

온라인저지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. 6. 3.
[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. 6. 2.
[BOJ] 5622번: 다이얼 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; } 2018. 6. 2.
[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. 6. 2.
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. 6. 1.
[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∑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. 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] 11819번: The Shortest does not Mean the Simplest 11819번: The Shortest does not Mean the Simplest 풀이 모듈러 연산의 특징 을 알고 있어야 풀 수 있는 문제다(+센스). 여기서는 모듈러의 곱셈, 덧셈 특징이 적용되기에 내용만 적자면 이렇다. 참고: 모듈러 연산 성질 곱셈: (A*B) mod C = ((A mod C) * (B mod C)) mod C 덧셈: (A+B) mod C = ((A mod C) + (B mod C)) mod C 제곱을 할 때 이것을 써야 하고, 사실 이 문제는 long long 범위를 곱할 때도 그냥 넘겨 버리기 때문에 우리가 쓰는 곱셈을 그냥 쓰면 안 되고 덧셈으로 바꿔서 계산해야 한다. 하지만 일반적인 생각으로 곱셈 구현을 하면 너무 느리기 때문에 a la russe 방식을 쓰면 된다. '.. 2018. 5. 21.
[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.

티스토리툴바