문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 이 문제는 다이나믹 프로그래밍을 이용해서 해결할 수 있다. Top-down 방식 혹은 Bottom-up 방식을 사용할 수 있는데, 나는 Bottom-up 방식을 사용하였다. dp 배열을 2차원 배열로 만들어서 사용하면 되는데, 그 의미는 다음과 같다. 예를 들어 dp[3][5]는 3번째 자릿수가 5일때 계단 수이다. 이걸 어떻게 구할 수 있을까? N=3일때 dp[3][5]는 dp[2][4] + dp[2][6] 이다. 즉, 두 번째 자릿수가 4이거나 6일때의 계단수를 더하면 된다. 이 때 주의해야 할 ..
문제 https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 풀이 이 문제는 간단한 정렬과 그리디 알고리즘을 적용하여 풀 수 있다. 먼저 크레인과 박스를 내림차순으로 정렬한다. 이후 크레인과 박스를 순차적으로 대조하여 옮길 수 있다면 박스 리스트에서 박스를 제거한다. 간단한 방법이지만, 자료구조를 어떤 것을 사용하냐에 따라서 시간초과가 발생할 수 있다. 나는 처음에는 box를 제거할 때 시간이 O(1)밖에 걸리지 않는 LinkedLis..
문제 https://www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 풀이 N,M이 최대 4이므로 최대 2(가로,세로)^16=65536의 경우의 수가 있으므로 브루트포스 방식으로 해결가능하다. 재귀형식으로 각 원소를 가로로 택할지 세로로 택할지 선택할 수 있겠지만, 비트마스킹을 사용하면 더 간단하다. 예를 들어 아래와 같은 예제를 보자. 비트가 0이면 해당 숫자는 가로, 1이면 세로라고 판단하자. [그림 1]의 왼쪽그림은 오른쪽처럼 나타낼 수 있다. 이를 마..
문제 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 풀이 나는 이 문제를 그리디 알고리즘을 사용해서 풀었다. 현재 점프할 수 있는 곳 중에서 그 칸에 도착했을 때 가장 멀리 갈 수 있는 곳으로 점프하면 가장 빠르게 도착할 수 있다. 현재 점프할 수 있는 곳 중에서 가장 멀리 점프한다는 뜻이 아니다! 예시를 보자. 아래와 같이 시작한다. 1 2 0 1 3 2 1 5 4 2 x 이 상황에서는 최대 한칸 밖에 못 가므로 그냥 한 칸을 뛴..
문제 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 풀이 이 문제는 두 가지 풀이가 가능하다. 첫번째는 Set을 이용한 방법이다. a + b = X 라는 식을 만족한다면, a = X-b 도 만족한다. 따라서 모든 원소를 Set에 넣은 다음, 첫 원소부터 탐색하며 X-i번째 원소가 Set에 존재한다면 두 수의 합이 X가 되는 것이므로 count 해준다. 이때 주의할 점은 이렇게 모든 원소를..
문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 풀이 처음 문제를 봤을 땐 DFS를 사용하면 간단하게 풀릴 것 같았다. 하지만 결과는 시간초과..... 이 문제는 단순히 DFS만을 사용하면 시간초과가 발생한다. DFS와 DP를 섞어서 사용해야 한다. 만약 DFS를 통해 모든 길을 탐색하던 도중 이미 탐색해서 경로를 계산한 좌표를 만난다면 굳이 다시 탐색을 할 필요는 없다. 따라서 이를 미리 저장해놓고 사용하면 된다. 코드 HTML 삽입 ..
문제 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 풀이 처음에는 자바 String의 split() 기능을 이용해서 쉽게 해결하려고 했다. 하지만 이 방법을 사용하면 메모리 초과가 발생해버린다. 그 이유는 자바의 String은 불변(immutable)이라서 값을 바꿀때마다 매번 새로운 String을 할당하기 때문이다. 따라서 이 문제는 스택 혹은 StringBuilder를 이용해서 풀어야한다. 풀이는 간단하다. StringBui..
문제 https://www.acmicpc.net/problem/1082 1082번: 방 번호 스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이고, M원을 모두 사용해 www.acmicpc.net 풀이 숫자를 사서 가장 큰 숫자를 만드려면 어떻게 해야 할까? 아래와 같은 우선순위를 고려해야 할 것이다. 1. 자릿수를 가장 길게 만든다. 2. 맨 앞자리부터 가장 큰 수가 들어가야 한다. 따라서 우선 가장 저렴한 숫자를 최대한 많이 사서 자릿수를 최대한 길게 만든다. 이때 가장 저렴한 숫자가 0이라면, 두 번째로 저렴한 숫자를 맨 앞에 두고 이후 0을 최대한 많이 사서 붙인다. 자릿수를 가장 ..
문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 이 문제는 배낭 문제(Knapsack)로 유명한 문제이다. 처음 이 문제를 봤을 땐 그리디 알고리즘을 떠올렸다. 하지만 그리디 알고리즘으로는 이 문제를 해결할 수 없다. 배낭 문제는 짐을 쪼갤 수 있는 경우는 Fraction Knapsack Problem이라고 하고 그리디 알고리즘으로 해결할 수 있다. 짐을 쪼갤 수 없는..