​​ BOJ 백준 11570 환상의 듀엣 문제: https://www.acmicpc.net/problem/11570 11570번: 환상의 듀엣 상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높 www.acmicpc.net 상덕이와 희원이 두 사람이 서로 노래를 부를 때 악보에 적혀 있는 N개의 음을 순서대로 노래한다. 악보에서 서로 인접한 두 음의 높이 차이의 합이 노래를 할 때 힘든 정도이다. 상덕이와 희원이가 한 악보에 있는 N개의 음을 분담하여 노래할 때, 두 사람 각각의 힘든 정도의 합의 최솟값을 구해야 한다. N개의 음을 두 집합 A, B로 나누고 모든 음이 ..

BOJ 백준 1648 격자판 채우기 문제: https://www.acmicpc.net/problem/1648 1648번: 격자판 채우기 준규는 침대에 누워서 천장을 바라보고 있었다. 천장은 격자판 모양이었고, 계속해서 천장을 바라보다 보니 이런 생각이 들었다. 세로 크기가 N이고, 가로 크기가 M인 격자판을 2x1 크기의 도미노 www.acmicpc.net N × M 크기의 격자판을 2 × 1 또는 1 × 2 크기의 도미노로 채우는 방법의 수를 구해야 한다. 2 × M 크기의 격자판을 채우는 문제(BOJ 11726번)를 이전에 푼 적이 있어서 이와 유사한 문제라고 생각하고 접근했다. 그러나 해결 방법을 고민하면서 이전 것과는 전혀 다른 문제임을 알았다. 처음에는 이전 문제처럼 왼쪽 열에서부터 오른쪽 열로..

BOJ 백준 19645 햄최몇? 문제: https://www.acmicpc.net/problem/19645 19645번: 햄최몇? 세 모질이들 관우, 철환, 길원이가 모였다. 모질이들은 모이면 서로 '햄버거 최대 몇 개 드실 수 있나요?'의 준말인 '햄최몇?'을 시전하며 자랑을 하기 바쁘다. 막내 길원이는 문득 중요한 사실을 www.acmicpc.net N개의 햄버거가 있고, 각 햄버거마다 먹을 때 얻을 수 있는 효용 값이 정해져 있다. 또한 섭취한 햄버거의 효용 값은 누적된다. 두 명의 선배와 막내 길원이가 모여서 N개의 햄버거를 먹을 때, 선배가 더 많은 효용을 얻게 하면서 막내가 얻을 수 있는 효용의 최댓값을 구하는 것이 문제이다. 처음에는 Dynamic Programming 풀이법으로 접근하여 다..

BOJ 백준 10160 암호 문제: https://www.acmicpc.net/problem/10160 10160번: 암호 새로 바뀐 KOI 웹사이트의 암호는 N개의 영문 알파벳 대문자로 이루어진다. 특별히 암호는 영문 알파벳 중 처음 K개를 사용해서 만든다. 예를 들어, K=5이면, ‘A', 'B', 'C', 'D', 'E'만으로 암호를 만들 www.acmicpc.net 길이가 N이고 영문 알파벳 중 처음 K개의 알파벳을 사용해서 만든 암호 중 안전한 암호의 개수를 구한다. 여기서 ‘안전한 암호’란 “ABCBC” 또는 “ABABC” 패턴이 없는 암호를 의미한다. 처음에는 여집합을 이용해서 구하는 방법을 고민했다. 전체 암호의 개수에서 안전하지 않은 암호의 개수를 구하면 안전한 암호의 개수를 알 수 있기..

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 이상일 때 현재 방문 중인 정점이 직전에 방문한 ..