CEO

문제 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 풀이 리스트를 만들 때, list[선택하고자 하는 아이템의 수][최대 가치]로 2차원 배열을 만든다. list[0]은 아무것도 연주하지 않은 상태, 최초에 볼륨을 적용한 상태이므로 list[0]의 값들은 0이다. 2중 반복문을 순회하면서 list[1], list[2] ... 로 접근하며 가방에 넣을 수 있는 아이템의 상태를 기록한다. n * m 만큼의 반복문을 순회하면, 최대 값어치을 체..

문제 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 문제 풀이 연주할 곡과 현재 볼륨, 최대 볼륨과 함께 각 곡을 연주할 수 볼륨 리스트가 주어진다. 조절할 수 있는 볼륨은 현재 연주곡이 1번이라면 볼륨 리스트 1번의 볼륨 크기만큼 추가하거나, 더하여 0보다 크거나 최대 볼륨보다는 작을 경우에만 연주가 가능하다. 만약 연주가 불가능하다 보면 -1을 출력하여야 한다. 처음 문제를 접하였을 때는 연주할 수 있는 볼륨을 -하거나 +하여야 하므로, DFS로 풀어야 한다고 생각하..

문제 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net 문제 풀이 버튼을 누를 수 있는 횟수 N이 주어질 때, A 버튼, Ctrl-A, Ctrl-C, Ctrl-V를 사용하여 가장 많이 A를 출력하는 횟수를 구하는 문제이다. 주어진 횟수 3, 7, 11의 규칙을 이끌어낼 수 있는 경우의 수를 찾으면 문제를 쉽게 해결할 수 있다. 우선 1에서 6까지는 A를 복사하는 경우보다 A를 입..

문제 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주�� www.acmicpc.net 문제 풀이 앞서 다룬 동전 1은 동전을 합하여 K가 되는 경우의 수를 찾는 문제였지만, 이 문제는 동전을 합하여 K가 될 때, 최소의 동전을 사용하여 K가 되는 경우를 반환하는 문제이다. 위와 같이 동전의 가치에 따라, 사용하여야 되는 동전의 개수를 구할 수 있다. 앞서 다룬 동전 1은 동전의 합이 K가 되는 경우의 수를 찾기 위해 경우의 수들을 누적하였다. 이와 달리 이 문제에서는 최초에 가장 작은 가치의 동전으로 금액을..

문제 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 다른 가치를 가진 동전이 주어질 때, 해당 동전들의 합으로 K가 되는 경우의 수를 구하는 문제이다. 문제를 풀기 위해서는 각 동전 별로 금액을 계산할 수 있는 경우의 수를 구하고 이를 메모이제이션을 통해 누적하여 답을 도출할 수 있다. 위와 같이 동전의 가치에 따라 발생할 수 있는 경우의 수를 구할 수 있다. 가장 작은 동전으로 구할 수 있는 경우의 수는 금액에 따라 1가지씩만 존재하게 된다. 하지만 그 다음으로 큰 가치의 동전에 대한 경우의 수를..

문제 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거�� www.acmicpc.net 문제 풀이 N X N 게임판이 주어질 때, 현재 경로에서 (0, 1), (1, 0)으로만 이동할 수 있다. 게임판에 주어진 숫자만큼 점프하여 이동하는 규칙이 적용될 때, (N, N)에 도달할 수 있는 경우의 수를 반환하는 문제이다. 이 문제는 단순히 보면 DFS나, BFS로 풀면 되겠지라고 생각되지만 N이 최대 100까지 커지므로 시간 초과가 발생하게 된다. 따라서 문제 분류와 같이 DP로 풀어야 한다. 현재 위치의 점프할 수 있는 거리를 x, y축에 각각..

문제 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net 문제 풀이 N X M의 미로가 주어질 때, 현재 위치에서 (1, 0), (0, 1), (1, 1)과 같은 경로로 이동할 수 있다. 왼쪽 가장 윗방에서 출발하여, 가장 오른쪽 끝인 N, M에 도착할 때 최대로 가져올 수 있는 사탕의 개수를 반환하면 된다. 문제를 풀기 위해서는 입력받은 그래프에 추가적으로 데이터를 줄 필요가 있다. 예를 들어 예제 입력 2는 다음과 같이 변환할 수 있다. 기존의 그래프를 위와 같이 변경하면 점화식 `graph..

문제 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 풀이 로봇 청소기의 동작 로직이 정해져고, 그래프가 주어질 때 최대 몇 칸을 청소할 수 있는지 반환하는 문제이다. 해당 문제에서 로봇 청소기는 다음과 같이 작동한다. 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다...