BOJ 백준 20925 메이플스토리 문제: https://www.acmicpc.net/problem/20925 20925번: 메이플스토리 첫째 줄 사냥터 수 $N$ ($1 \le N \le 200$)과 방학 기간을 분 단위로 나타낸 $T$ ($1 \le T \le 1\,000$)가 주어진다. 다음 $N$개의 줄에는 $i$번째 사냥터의 특징인 입장에 필요한 최소 경험치 $c_i$와 $1$분마 www.acmicpc.net 메이플스토리 게임에는 여러 사냥터가 있는데, 각 사냥터는 입장에 필요한 최소 경험치와 1분마다 얻는 경험치 값을 지닌다. 상원이는 T분 동안 N개의 모든 사냥터 중 하나 이상의 임의의 사냥터에서 경험치를 얻는다. 사냥을 시작하고 매 분마다 현재 사냥터에서 다른 사냥터로 갈지 결정할 수 있고..

​​ BOJ 백준 5444 시리얼 넘버 문제: https://www.acmicpc.net/problem/5444 N개의 기타가 존재하고, 이 중에는 강토가 갖고 있는 기타가 있다. 강토가 소유하는 기타의 시리얼 넘버를 모두 합한 값은 M의 배수이다. N개의 모든 기타의 시리얼 넘버와 M이 주어졌을 때, 가능한 강토의 기타 개수의 최댓값을 구해야 한다. 다음과 같은 배열을 정의하면 동적 프로그래밍(Dynamic Programming)으로 해결 가능하다. dp[i][j]: i번째 기타까지 봤고, 이 중에서 강토가 갖고 있는 기타의 시리얼 넘버 합을 M으로 나누었을 때의 값이 j일 때의 가능한 강토의 기타 개수의 최댓값 아래는 풀이 과정을 정리한 것이다. 1) 우선 dp 배열 값을 모두 -1로 초기화한다. 2..

BOJ 백준 12861 죄수에게 주는 뇌물 문제: https://www.acmicpc.net/problem/12861 12861번: 죄수에게 주는 뇌물 세계적인 BOJ 감옥에는 방 P개가 1열로 늘어서 있다. 좌측 방부터 순서대로 1, 2, ... P란 번호가 붙어 있다. 모든 방은 독방으로, 각 방에 한 명의 죄수가 수감되어 있다. 각각의 방 사이에는 창문이 www.acmicpc.net 일렬로 된 P개의 감옥방에서 정해진 Q명의 죄수를 석방해야 한다. 어떤 한 죄수를 석방할 때 그 죄수 방의 바로 옆 방의 죄수들에게 뇌물을 줘야 하며, 옆 방의 또 옆 방에 있는 죄수들에게도 뇌물을 줘야 한다. 즉, 중간에 석방된 죄수로 인해 끊기는 지점 전까지 전달 가능한 죄수들에게 모두 금화 1개씩 뇌물로 줘야한다...

​​ BOJ 백준 16964 DFS 스페셜 저지 문졔: https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 트리와 트리의 노드를 방문한 순서가 주어졌을 때, 올바른 DFS 방문 순서가 맞는지를 구하는 문제이다. DFS(Depth First Search) 순서를 만족하는 조건을 먼저 생각해봤다. 1) 직전에 방문한 정점의 자식들 중에서 방문하지 않은 정점의 수가 1 이상일 때 현재 방문 중인 정점이 직전에 방문한 ..

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번째 이..