plzfday's notes

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]의 값으로 업데이트한다. 또한 남녀 입력 받은 수열을 정렬해줘야 하는데 그..

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

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; }

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

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

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

2607번: 비슷한 단어 문제 요약 조건에 따라 첫 번째 단어와 비슷한 단어의 개수를 출력한다. 조건 같은 구성이란: 두 단어가 같은 종류의 문자로 이루어져 있다. 같은 문자는 같은 개수만큼 있다. 같은 종류의 문자가 같은 개수만큼 있거나, 한 단어에서 문자를 더하거나 빼거나 한 문자를 다른 문자로 바꾸거나 해서 같은 구성을 만들면 비슷한 단어로 취급한다. 단어의 변형을 한 번만 할 수 있기 때문에 단어의 길이 차이가 1 이하여야 한다. 그리고 문자 차이가 2개 이하여야 한다. BOJ, BOI 두 단어가 있을 때, 문자의 차이는 2개다. 그렇지만 I를 J로 바꿔주면 비슷한 단어가 된다. 코드 #include using namespace std; int n, ans = 0; bool check(const ..

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

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

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