sort6 [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] 11508번: 2+1 세일 https://www.acmicpc.net/problem/11508 어차피 가격 제일 낮은 건 3개 묶은 거에서 공짜이므로 미리 정렬을 시켜놓고 순차적으로 확인하자. (예전에 짠 코드라 sort를 직접 구현했다..) #include #include int price[100001]; void quickSort(int arr[], int left, int right); int main(void) { int n, sum = 0; scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &price[i]); quickSort(price, 0, sizeof(price) / sizeof(price[0]) - 1); for (int i = 0; i < n; ++i) { s.. 2018. 7. 27. [BOJ] 11650번: 좌표 정렬하기 https://www.acmicpc.net/problem/11650 문제에서 하라는데로만 하면 되는데 COMP함수만 잘 짜면 된다.(주어진 조건에 따라서...) STL을 연습하는 문제였다. #include #include #include #include using namespace std; bool COMP(const pair &a, const pair &b) { if (a.first == b.first) return a.second < b.second; return a.first < b.first; } int N; vector v; int main() { scanf("%d", &N); for (int i = 0, a, b; i < N; ++i) { scanf("%d %d", &a, &b); v.push.. 2018. 7. 26. [BOJ] 2750번: 수 정렬하기 https://www.acmicpc.net/problem/2750 정말 여러 가지 방법으로 풀 수 있다. 우선순위 큐, 정렬 등등... (아마 set이나 map으로도 가능할 거다) 우선순위 큐는 기본적으로 큰 수부터 pop 하기 때문에 -를 붙여서 넣어주고 -를 붙여서 빼주면 오름차순으로 pop 할 수 있게 된다. 아니면 우선순위 큐 정의할 때 의 greater를 사용하면 가능하긴 하지만 귀찮으니까 위의 방법을 애용하자. // 우선순위 큐로 해결하기 #include #include using namespace std; priority_queue pq; int main() { int n; scanf("%d", &n); for (int i = 0, a; i < n; ++i) { scanf("%d", &a);.. 2018. 7. 26. [BOJ] 3047번: ABC 3047번: ABC 숫자 3개를 정렬하면 쉽게 풀 수 있다. 코드 #include using namespace std; int main() { int al[3]; char str[4]; scanf("%d %d %d %s", &al[0], &al[1], &al[2], str); sort(al, al + 3); printf("%d %d %d", al[str[0] - 'A'], al[str[1] - 'A'], al[str[2] - 'A']); return 0; } 2018. 7. 19. [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. 이전 1 다음