1. 방 배정 https://www.acmicpc.net/problem/13300 학생들을 학년별, 성별로 한 방에 배정하려고 하는데 필요한 최소 방의 개수를 구하는 문제다. 문제에서 요구하는 대로 학년별, 성별로 인원을 센 다음에 각각에 대해 최소로 필요한 방의 개수를 센 뒤 더해주면 된다. 이는 나눗셈과 나머지 연산으로 쉽게 구할 수 있다. #include int n, k, s, y, C[7][2]; int main() { scanf("%d%d", &n, &k); while (n--) { scanf("%d%d", &s, &y); ++C[y][s]; } int ans = 0; for (int i = 1 ; i
문제 링크 https://www.acmicpc.net/problem/5626 문제 요약 현재 제단의 상태가 주어진다. 도둑이 훔쳐간 부분은 -1이고 남아있는 부분은 정수로 표현이 되어있다. 이 때 가능한 초기 제단의 경우의 수를 구하는 문제다. 문제에서 초기 제단을 만드는 방법은 주어진다. 문제 풀이 모든 열의 초기값은 0이다. 이 때 한가지 연산을 할 수 있다. 같은 높이를 가지는 연속하는 열들을 선택한다. 그리고 선택한 연속된 열 중 처음 열과 가장 끝 열을 제외한 모든 열의 높이를 1씩 높인다. 이 연산을 사용해서 제단을 만들어 나갈 수 있다. 이 연산을 잘 생각해 본다면 두가지 통찰을 얻을 수 있다. 1. 첫 번째 제단과 마지막 열의 높이는 0이다. 2. 인접한 두 열의 높이차는 최대 1이다. 이..
문제 링크 https://www.acmicpc.net/problem/1637 문제 요약 정수가 여러개 모여있는 정수더미가 있다. 이 때 정수더미 안에서 홀수개 들어있는 특정 정수를 찾는 문제다. 홀수개 들어있는 정수의 수는 최대 한개이며 없을수도 있다. 문제 풀이 이 문제는 정수가 직접 주어지는게 아니라 정수더미 안에 들어있는 수들의 규칙이 주어지고 이를 통해 홀수개 들어있는 정수를 찾아야 하기 때문에 단순 시뮬레이션으로는 풀수가 없다. 그렇다면 어떻게 접근해야 할까? 우선 예제의 수들을 한번 직접 계산해보자. 직접 계산해 본다면 숫자 4가 3개 들어있어서 답이 됨을 알 수 있다. 이것만으로 일정한 규칙을 찾을수가 없다. 하지만 이들 수의 누적합을 계산해 본다면 특정 규칙을 찾을 수 있다. 위 표를 잘 ..
- Total
- Today
- Yesterday
- disjoint set
- brute force
- Data Structure
- max flow
- Binary Search
- Sqrt Decomposition
- DP
- bipartite matching
- graph
- greedy
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |