본문 바로가기

PS23

[BOJ] 1727번: 커플 만들기 https://www.acmicpc.net/problem/1727 남자를 기준으로 잡고 풀었다. D[i][j]: i번째 남자까지와 j번째 여자까지 짝을 맺었을 때 성격 차이의 최소합 D[i][j] = D[i - 1][j - 1] + abs(man[i] - girl[i]) if(i > j) D[i][j] = D[i - 1][j] - 남자가 여자보다 많아서 짝을 지을 수 없음 if(i 사실 이렇게 생각하는게 맞는지 모르겠다. 어쨋거나 핵심인 짝을 만들거나, 만들지 않거나를 점화식으로 세운 것이다. 저 세 식 중 최소인 값을 D[i][j]의 값으로 업데이트한다. 또한 남녀 입력 받은 수열을 정렬해줘야 하는데 그.. 2018. 8. 4.
[BOJ] 2587번: 대표값2 2587번: 대표값2 풀이 5개로 고정되어 있는 자연수가 주어지기 때문에 중앙값은 정렬 후에 v[2]가 된다. 코드 #include using namespace std; vector v; int sum = 0; int main() { cin.tie(0); ios_base::sync_with_stdio(false); for (int i = 0, a; i > a; sum += a; v.push_back(a); } sort(v.begin(), v.end()); cout 2018. 7. 13.
[BOJ] 2588번: 곱셈 2588번: 곱셈 풀이 ㅁㄴㅇㄹ... 간단하게 생각하자. 코드 #include using namespace std; int main() { ios_base::sync_with_stdio(false), cin.tie(0); int n1, n2; scanf("%d %d", &n1, &n2); printf("%d\n%d\n%d\n%d", n2 % 10 * n1, n2 % 100 / 10 * n1, n2 / 100 * n1, n1 * n2); return 0; } 2018. 7. 13.
[BOJ] 2609번: 최대공약수와 최소공배수 2609번: 최대공약수와 최소공배수 풀이 gcd, lcm코드 정도는 외워놓으면 좋다. 구현하는 것이 문제이기 때문에 어려운 것은 없었다. 코드 #include using namespace std; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int lcm(int a, int b, int c) { return a * (b / c); } int main() { cin.tie(0); ios_base::sync_with_stdio(false); int a, b; cin >> a >> b; int tmp = gcd(a, b); cout 2018. 7. 13.
[BOJ] 10800번: 컬러볼 10800번: 컬러볼 풀이 지역본선 2015에서 초등부 4번, 고등부 2번으로 나왔던 문제다. 예전에 한 번 풀어본 적이 있었는데 무식하게 으로 풀었다가 당연히 시간 초과를 맞았다 ㅋㅋ 우선 이건 내 머리에서 나온 풀이가 아니다. 사이즈 별로 정렬하는 것까진 생각했는데 색을 어떻게 처리해야 할 지 몰랐다. (왜 그랬는지 모르겠다) CODER's BRUNCH님 블로그 그래도 지금은 완전히 이해했으니 정리하는 겸 써보겠다... N ball[j].s; ++j) { accul += ball[j].s; colorSum[ball[j].c] += ball[j].s; } ret[ball[i].idx] = accul - colorSum[ball[i].c]; } for (int i = 0; i < N; ++i) print.. 2018. 7. 13.
[BOJ] 2608번: 로마 숫자 2608번: 로마 숫자 어렵다고 생각했는데 어떻게 변수를 잘 저장하고 사용하느냐를 물어보는 듯한 문제였다. token[][3] = {"IV", "XL", "CD", "M"}; 이렇게 저장하는 게 핵심이었던 것 같다. 코드 #include using namespace std; char s[11], token[][3] = {"IV", "XL", "CD", "M"}; // 4, 40, 400, 1000 int roman[90], ans = 0; const int divs = 1000, zerocnt = 3; int main() { cin.tie(0); ios_base::sync_with_stdio(false); roman['I'] = 1, roman['V'] = 5, roman['X'] = 10, roman[.. 2018. 7. 12.
[BOJ] 2607번: 비슷한 단어 2607번: 비슷한 단어 문제 요약 조건에 따라 첫 번째 단어와 비슷한 단어의 개수를 출력한다. 조건 같은 구성이란: 두 단어가 같은 종류의 문자로 이루어져 있다. 같은 문자는 같은 개수만큼 있다. 같은 종류의 문자가 같은 개수만큼 있거나, 한 단어에서 문자를 더하거나 빼거나 한 문자를 다른 문자로 바꾸거나 해서 같은 구성을 만들면 비슷한 단어로 취급한다. 단어의 변형을 한 번만 할 수 있기 때문에 단어의 길이 차이가 1 이하여야 한다. 그리고 문자 차이가 2개 이하여야 한다. BOJ, BOI 두 단어가 있을 때, 문자의 차이는 2개다. 그렇지만 I를 J로 바꿔주면 비슷한 단어가 된다. 코드 #include using namespace std; int n, ans = 0; bool check(const .. 2018. 7. 12.
[BOJ] 11048번: 이동하기 11048번: 이동하기 풀이 간단히 바로 생각나는 점화식은 dp[i][j]=max(dp[i−1][j],dp[i−1][j−1],dp[i][j−1])dp[i][j] = max(dp[i - 1][j], dp[i - 1][j-1], dp[i][j-1])dp[i][j]=max(dp[i−1][j],dp[i−1][j−1],dp[i][j−1])인데 캔디 개수로 음수가 나올리가 없으므로 dp[i−1][j−1]dp[i-1][j-1]dp[i−1][j−1]을 도는 것은 사치다. 최대한 많이 얻어야 좋은 건데 바로 한 단계를 건너뛰는 것은 엄연한 사치다. 그래서 dp[i][j]=max(dp[i−1][j],dp[i][j−1])dp[i][j] = max(dp[i - 1][j], dp[i][j-1])dp[i][j]=max(dp[i−.. 2018. 6. 4.
[BOJ] 1932번: 정수 삼각형 1932번: 정수 삼각형 풀이 현재 칸을 기준으로 이전 칸에서 좌, 우를 비교해서 최댓값을 계속 축적해주면 된다. 그리고 마지막 줄을 순회하면서 최댓값을 구하는 방법. 코드 예전에 짠 코드 #include const int MAX = 501; int N, max = -1, i, j; int v[MAX][MAX]; void input() { scanf("%d", &N); for (int i = 1; i 2018. 6. 4.
[BOJ] 11057번: 오르막 수 11057번: 오르막 수 풀이 우선 본 문제의 아이디어는 쉬운 계단 수에서 가져왔다. 굉장히 유사한 방법(거의 똑같다)으로 풀 수 있었다. D[i][j]는 길이가 i이고 끝자리 숫자가 j인 오르막 수 따라서 i - 1 길이, 끝자리 숫자가 현재 j보다 작은 오르막 수들의 경우의 수를 누적 시키면 된다. 코드 #include int n, D[1001][10]; const int div = 10007; int main() { scanf("%d", &n); for (int i = 0; i 2018. 6. 3.
[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.

티스토리툴바