My life story

1. 문제 링크 https://www.acmicpc.net/problem/2367 2367번: 파티 첫째 줄에는 N, K, D가 주어진다. 다음 줄에는 D개의 정수가 주어지는데, 이는 각 음식의 종류마다 가져올 수 있는 양의 제한을 의미한다. 다음 N개의 줄에는 각 사람이 요리할 줄 아는 음식의 종류 www.acmicpc.net 2. 문제 개요 N(3 ≤ N ≤ 200) 명의 사람이 파티를 하려고 한다. 각각의 사람은 몇 종류의 음식을 요리할 줄 안다. 각 음식의 종류는 1부터 D(5 ≤ D ≤ 100) 까지의 정수로 표현된다. 각각의 사람이 가져올 수 있는 음식의 양에 제한이 있다. 각각의 사람은 최대 K(1 ≤ K ≤ 5) 개의 접시 밖에 가져올 수 없다. 이때, 같은 종류의 음식은 한 접시밖에 가져..

1. 문제 링크 www.acmicpc.net/problem/11495 11495번: 격자 0 만들기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n과 m (2 ≤ n, m ≤ 50)이 주어지며, n은 격자의 행 개수, m은 격자의 열 개수를 나타낸다. 그 다음 n개의 줄에 각각 www.acmicpc.net 2. 문제 개요 음수가 아닌 정수들의 격자가 주어진다. - 격자에서 가로 또는 세로로 인접한 정수 2개를 고른다. - 각 정수가 양수일 때 1 감소시킨다. 격자가 주어졌을 때 모든 정수를 0으로 만들기 위해 필요한 최소 연산의 횟수를 구하는 프로그램을 작성하시오. 3. 문제 힌트 우선, [0, 1] 을 선택했을 때, [-1, 0]이 되는 게 아닌가.. 생각했는데, 문..

1. 문제 링크 www.acmicpc.net/problem/11406 11406번: 책 구매하기 2 총 N명의 사람이 책을 구매하려고 한다. 각 사람은 1번부터 N번까지 번호가 매겨져 있고, 각 사람이 사려고하는 책의 개수는 A1, A2, ..., AN권이다. 이 책을 판매하는 온라인 서점은 총 M곳이 있다.각 www.acmicpc.net 2. 문제 개요 N명의 사람이 각자 A_j권의 책만큼 책을 구매하려고 한다. 서점은 M개가 있다. 서점에는 B_i권의 책이 있다. 사람 j가 서점 i에서 살 수 있는 최대 책의 개수는 C_ij이다. 이때, 사람들이 책을 가장 많이 사려고 할 때, 최대 몇 권까지 살 수 있는지 구하는 프로그램을 작성하시오. 3. 문제 힌트 최대유량으로 풀 수 있을 것 같다. 사람이 살 ..

1. 문제 링크 www.acmicpc.net/problem/17412 17412번: 도시 왕복하기 1 첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 출발 도시와 도착 도시의 번호가 주어지며, 두 번호는 다르다. www.acmicpc.net 2. 문제 개요 N개의 도시가 P개의 단방향 길로 연결되어 있다. 1번 도시에서 시작해서 2번 도시로 가야 하는데, 한번 경로에 포함된 길은 다시 포함되어서는 안된다. 이때, 1번 도시에서 2번 도시까지 갈 수 있는 경로의 개수를 구하는 프로그램을 작성하시오. 3. 문제 힌트 단 한번만 가야 한다..라는 것의 의미를 다시 생각해보자. 한번 가고 나면 간선(경로, 도로)이 막히는 그런 게..

1. 문제 링크 https://www.acmicpc.net/problem/2316 2316번: 도시 왕복하기 2 N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방문했던 도시(1, 2번 도시 제외)를 두 번 이상 방문하지 않으려 한다. 한 번 1번 도시와 2번 도시 사이를 오갈 때, 반드시 한 개 이상의 도시를 중간에 거쳐야 한다. 입력에는 1번 도시와 2번 도시를 연결하는 길은 없다. 도시의 번호는 1번부터 N번까지이다 www.acmicpc.net 2. 문제 개요 N개의 도시가 P개의 양방향 길로 연결되어 있다. 1 --- 2 번 도시를 오갈 때, 반드시 1..

1. 문제 링크 https://www.acmicpc.net/problem/11378 11378번: 열혈강호 4 첫째 줄에 직원의 수 N과 일의 개수 M, 지난달에 받은 벌점의 합 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다. www.acmicpc.net 2. 문제 개요 직원 N명 일 M개가 있다. 벌점을 X점 받은 사람은 일을 최대 X+1개 할 수 있다. 하지만 누가 X점을 받았는지는 모르고 저번 주에 받은 벌점의 합계는 안다. 적절히 배분해야 한다. N, M, X가 주어 졌을 때 일을 최대 몇 개를 할 수 있는지 구하는 프로그램 작성. 3. 문제 힌트 최대 유량 알고리..