BOJ 백준 15553 난로 문제: https://www.acmicpc.net/problem/15553 구사과의 방에는 N명의 친구가 오고, 구사과는 친구가 왔을 때 항상 방에 있는 난로를 켠다. 구사과의 방에는 구사과를 포함하여 최대 두 명만 들어올 수 있고, i 번째로 방문하는 친구는 T[i]에서 T[i] + 1 시간에만 방에 있다. 난로를 켤 성냥은 K개만 주어지는데, 난로를 한 번 켤 때 하나의 성냥이 필요하다. 이때 난로가 켜져 있는 시간의 최솟값을 구해야 한다. 우선 예제 입력을 사용하여 어떻게 문제 풀이를 최적화할 수 있을지 고민해 봤다. 다음과 같은 상태라고 가정하자. N = 10, K = 5, T[i] = {1, 2, 5, 6, 8, 11, 13, 15, 16, 20} x축을 방문하는 시..

BOJ 백준 1315 RPG 문제: https://www.acmicpc.net/problem/1315 1315번: RPG 준규는 새 RPG 게임을 시작했다. 이 게임에서 캐릭터는 2가지 스탯을 가지고 있다. 하나는 힘(STR)이고, 다른 하나는 지력(INT)이다. 캐릭터를 생성했을 때, 두 스탯은 모두 1이다. 게임에는 총 N개의 www.acmicpc.net RPG 게임에서 캐릭터의 스탯으로 힘(STR)과 지력(INT) 2가지가 존재하고, 처음 생성했을 때 스탯은 모두 1이다. 게임에는 하나 당 한 번만 깰 수 있는 총 N개의 퀘스트가 존재한다. i번째 퀘스트를 깨는 데 필요한 STR를 STR[i], INT를 INT[i]라고 할 때, 이를 깨려면 캐릭터의 STR가 STR[i] 이상이거나 캐릭터의 INT가..

BOJ 백준 1374 강의실 문제: https://www.acmicpc.net/problem/1374 1374번: 강의실 첫째 줄에 강의의 개수 N(1≤N≤100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번 www.acmicpc.net 한 강의실에서는 둘 이상의 강의를 동시에 진행하지 못하고 오직 하나의 강의만 진행 가능할 때, N개의 모든 강의를 끝내는 데 필요한 최소 강의실 수를 구해야 한다. 처음 문제를 보고 탐욕 알고리즘(Greedy Algorithm)으로 해결하는 문제임을 눈치챘다. 난이도가 크게 어렵지 않으면서 주어진 데이터를 정렬하여 풀어야 하는 탐욕 알고리즘 문제의 경..

BOJ 백준 2201번 이친수 찾기 문제: https://www.acmicpc.net/problem/2201 2201번: 이친수 찾기 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 들 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 이진수 중에서 다음과 같은 성질을 만족하는 것들을 이친수라고 하자. 1. 이친수는 0으로 시작하지 않는다. 2. 이친수에서는 1이 두 번 연속으로 니타나지 않는다. 이와 같은 이친수를 이진수의 크기 순서대로 정렬하여 차례로 번호를 붙였을 때, K번째 이친수를 찾아야 한다. 우선 각 자리 수마다 이친수가 몇 개 존재하는지를 구해서 K번째 이..

BOJ 백준 10423 전기가 부족해 문제: www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net N개의 도시, 설치 가능한 케이블 M개, 그리고 K개의 발전소가 있다. 도시가 발전소에 연결되면 발전소에 의해 생산된 전기가 연결된 도시에 공급된다. N개의 도시 모두 전기를 공급받을 수 있도록 설치해야 하는 케이블의 최소 비용을 구해야 한다. 단, 한 개의 도시는 반드시 한 개의 발전소에 의해서만 전기를 공급받아야 한다. ..

BOJ 백준 3665 최종순위 문제: www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 1번부터 n번까지 번호가 매겨진 팀들이 작년과 올해 대회에 참전했는데, 문제에서 알려주는 데이터는 작년 대회에서의 최종 순위와 올해 대회에서 상대적인 순위가 바뀐 팀들의 목록이다. 이를 바탕으로 올해 최종 순위를 구해야 하는데, 최종 순위가 완성될 수 없는 경우도 고려해야 한다. 이와 같은 경우는 다음과 같다. 1) 데이터의 일관성이 없는 경우 2) 확실한 순위를 찾..

BOJ 백준 2184 김치배달 문제: www.acmicpc.net/problem/2184 2184번: 김치 배달 첫째 줄에 두 정수 N, L이 주어진다. L은 김치 공장의 x좌표이다. 다음 N개의 줄에는 김치를 배달할 도시의 x좌표가 주어진다. 모든 좌표는 1이상 1,000,000이하의 정수이다. www.acmicpc.net ​ 김치 N 개를 N 개의 도시들에 배달하는데, 김치 공장과 각각의 도시들은 1차원 직선상의 점에 위치해 있다. 이 좌표계의 좌표 값은 정수임을 전제로 한다. 김치를 각 도시에 배달하면서 1차원 직선을 따라 1초에 한 칸씩 움직일 수 있고, 김치는 1초에 1만큼씩 쉬게 된다. 그리고 각 도시에 도착하는 그 순간 김치가 배달되는 것으로 가정한다. 즉, 어떤 도시에 도착하는 순간 해당 ..

BOJ 백준 8895 막대 배치 문제: www.acmicpc.net/problem/8895 8895번: 막대 배치 높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자. www.acmicpc.net ​ 높이가 1, 2, ... , n인 막대 n 개가 주어지고, 왼쪽에서 봤을 때 L 개, 오른쪽에서 봤을 때 R 개가 보이도록 막대를 배치하는 경우의 수를 구하는 것이 목표이다. 문제에서 높이가 1, 2, ... , n인 막대 n 개가 일렬로 배치되어 있다는 점에 주목했다. 막대가 n 개 있는데 굳이 높이가 1부터 n까지 한 개씩 있는 것은 일반적인 경우는 아니..