boj, 백준) 11407. 책 구매하기 3 (C/C++)
1. 문제 링크 www.acmicpc.net/problem/11407 11407번: 책 구매하기 3 총 N명의 사람이 책을 구매하려고 한다. 각 사람은 1번부터 N번까지 번호가 매겨져 있고, 각 사람이 사려고하는 책의 개수는 A1, A2, ..., AN권이다. 이 책을 판매하는 온라인 서점은 총 M곳이 있다.각 www.acmicpc.net 2. 문제 개요 총 N명의 사람이 M개의 서점에서 책을 사려고 한다. 각 사람은 사려고 하는 책의 개수가 정해져 있고 서점도 팔 수 있는 책의 개수가 정해져 있다. i번째 서점에서 j번째 사람에게 C_ij개의 책을 팔 수 있고, 이때 택배로 보내는 비용이 D_ij라고 할 때, 책을 최대 몇 권 살 수 있는지, 그리고 이때의 배송비의 합의 최솟값을 구하는 프로그램을 작성..
boj, 백준) 11406. 책 구매하기 2 ( C/C++)
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. 문제 힌트 최대유량으로 풀 수 있을 것 같다. 사람이 살 ..
boj, 백준) 17412. 도시 왕복하기1 (C/C++)
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. 문제 힌트 단 한번만 가야 한다..라는 것의 의미를 다시 생각해보자. 한번 가고 나면 간선(경로, 도로)이 막히는 그런 게..
boj, 백준) 2-SAT - 1
1. 문제 링크 www.acmicpc.net/problem/11277 11277번: 2-SAT - 1 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 20)과 절의 개수 M (1 ≤ M ≤ 100)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 양수인 www.acmicpc.net 2. 문제 개요 2-SAT를 풀어보자. SAT에 대한 설명은 본문에 잘 나와있다. 3. 문제 힌트 N은 최대 20, M은 최대 100, 전수조사로 충분히 풀 수 있는 크기이다. 시간 복잡도는 모든 경우의 수 (2^20)에 대해 M개의 식을 검증하면 된다. O(2^(N)*M)인데 간당간당.. 4. 문제 풀이 dfs방식으로 모든 순열을 만들어..
boj, 백준) 4013. ATM (C/C++)
1. 문제 링크 www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net 2. 문제 개요 모든 도로들이 일방통행으로 되어 있다. 도로들이 만나는 모든 교차로에는 ATM기가 설치되어 있다. 또, 일부 교차로에는 레스토랑이 있는데, ATM에 들릴 때마다 돈을 인출한다. 이때, 시작점에서 아무 레스토랑까지 최대한 많은 돈을 인출하여 레스토랑에 가려고 하는데, 이때 최대 얼마를 가지고 갈 수 있는지 구하는 프로그램을 작성. 3. 문제 힌트 문제를 보아하니.. ..
boj, 백준) 3977. 축구전술(C/C++)
1. 문제 링크 www.acmicpc.net/problem/3977 3977번: 축구 전술 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역 www.acmicpc.net 2. 문제 개요 경기장을 여러 개의 구역으로 나누고, 어떤 선수가 A구역에서 B구역으로 이동하게 하는 움직임을 (A,B)로 표현한다. 다른 모든 구역에 도달할 수 있는 시작 구역을 찾은 뒤 지시한 움직임만을 따라가라고 했다. 그런데 이러한 시작 구역을 찾는 것이 어려웠다. 적절한 시작 구역을 찾는 프로그램을 작성하시오 3. 문제 힌트 어떠한 시작점을 찾아서 그래프를 전부 순회할 ..