boj, 백준) 2151. 거울 설치 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다. www.acmicpc.net 2. 문제 개요 채영이네 집에 대한 정보가 주어졌을 때, 한쪽 문에서 다른 쪽 문을 볼 수 있도록 하기 위해 설치해야 하는 거울의 최소 개수를 구하는 프로그램을 작성하기. 3. 문제 힌트 ※구현 - BFS - 반사되는2가지, 거울을 놓지 않았다 생각하고 ..
boj, 백준) 3079. 입국심사 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/3079 3079번: 입국심사 문제 상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다. 가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사 www.acmicpc.net 2. 문제 개요 친구들은 총 M명이고, 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. ..
boj, 백준) 11408. 열혈강호 5 ( C/ C++ )
1. 문제 링크 https://www.acmicpc.net/problem/11408 11408번: 열혈강호 5 강호네 회사에는 직원이 N명이 있고, 해야 할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 각각의 직원이 할 수 있는 일의 목록과 그 일을 할 때 강호가 지급해야 하는 월급이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지, 그리고 그 때 강호가 지불해야 하는 월급의 최솟값을 구하는 프로그램을 www.acmicpc.net 2. 문제 개요 직원이 N 명, 일이 M개가 있다. 모두 1번부터 N번, 1번부터 M번까지 번호가 매겨져 있다. ..
boj, 백준) 2585. 경비행기 ( C/ C++)
1. 문제 링크 https://www.acmicpc.net/problem/2585 2585번: 경비행기 경비행기 독수리호가 출발지 S에서 목적지 T로 가능한 빠른 속도로 안전하게 이동하고자 한다. 이때, 경비행기의 연료통의 크기를 정하는 것이 중요한 문제가 된다. 큰 연료통을 장착하면 중간에 내려서 급유를 받는 횟수가 적은 장점이 있지만 연료통의 무게로 인하여 속도가 느려지고, 안정성에도 문제가 있을 수 있다. 한편 작은 연료통을 장착하면 비행기의 속도가 빨라지는 장점이 있지만 중간에 내려서 급유를 받아야 하는 횟수가 많아지는 단점이 있다. 문제는 중간에 www.acmicpc.net 2. 문제 개요 경비행기가 출발지 S에서 목적지 T로 이동하고자 한다. 이때 연료통의 크기를 정하는 것이 중요한 문제가 된..
boj, 백준) 11378. 열혈강호 4 ( C / C++ )
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. 문제 힌트 최대 유량 알고리..
boj, 백준) 11377. 열혈강호 3 ( C / C++ )
1. 문제 링크 https://www.acmicpc.net/problem/11377 11377번: 열혈강호 3 첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다. www.acmicpc.net 2. 문제 개요 직원 N명, M개의 일 N명 중에서 K명은 일을 최대 2개 할 수 있을 때, 일을 최대 몇 개를 할 수 있는지 구하는 프로그램 작성하기. 3. 문제 힌트 K명은 일을 한번 더 할 수 있다는 말은 일 1개씩 하는 이분매칭 + 최대 K = 답이 된다. 즉, 이분탐색을 한번 더 하고 누가 됐든 간에 어느..