[백준 / BOJ] 2342 Dance Dance Revolution
문제 출처 : www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 승환이는 DDR게임을 할려고한다. 중앙, 위, 왼쪽, 아래, 오른쪽 순서로 0, 1, 2, 3, 4 라고 할때, 승환이가 눌러야할 방향이 순서대로 주어진다. 한 위치에서 다른 위치로 발을 이동시킬때드는 힘의 크기가 다를때, 모든 방향을 누를때 드는 최소힘의 크기를 구하는 문제다. 풀이 BFS나 DP로 풀리는 문제다. 왼쪽발을 움직여서 해당 숫자를 누르는게 당장은 ..
[백준 / BOJ] 2056 작업
문제 출처 : www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net N개의 수행할 작업과, 각 작업을 수행하는데 걸리는 시간이 주어진다. 작업에는 선행관계가 있고, 각 작업을 수행하기위해선, 해당 작업의 선행작업을 수행해야한다. 이때, 모든 작업을 수행하는데 걸리는 최소시간을 구하는 문제다. 풀이 재귀와 메모이제이션으로 풀리는문제다. 현재 작업 A를 수행해야하고 A의 선행 작업이 B,C,D라고 할때, B,C,D가 걸리는 수행시간중 최댓값을 가져와서 A가 ..
[백준 / BOJ] 1149 RGB거리
문제 출처 : www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 집의수 N이 주어진다. 이때, 각 집은 빨강,초록,파랑으로 칠할수있고, 색깔은 연속되게 칠하지못한다. 각 색깔로 칠하기위해 드는 비용이 주어졌을때 최솟값을 구하는 문제다. 풀이 N이 최대 1000이고, 시간제한이 0.5라서 완탐으로 풀경우 시간초과가 난다. Dp를 이용하면 풀리는 문제였다. 각 색깔을 연속으로 칠할수없다는 조건이있다. 즉, 현재 색 R, G, B를 칠하기 위해..
[백준 / BOJ] 1082 방 번호
문제 출처 : www.acmicpc.net/problem/1082 1082번: 방 번호 문방구에서 파는 숫자의 개수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 문방구에서 파는 숫자는 0보다 크거나 같고, N-1보다 작거나 같은 자연수이다. 예를 들어, N=4이면, 문방구에서 파 www.acmicpc.net 갖고있는돈이 주어지고, 각 숫자들의 가격이주어진다 (0~9번까지숫자들의 가격) 이때, 숫자들을 조합해서만들수있는 최댓값을 찾는 문제다. 예를들어, 예제 1의경우, 순서대로 숫자 2를 8원에사고 숫자 1을 7원에 , 숫자 0을 6원에사면, 총 21원으로 210이 만들어지고 이때 최댓값을 갖는다. 풀이 완전탐색으로 풀경우, 최악의 경우, 총 10개의 글자가 중복을 허용해서 50개의 자리에 올수..