기맹기 개발 블로그

BOJ 17404 RGB거리 2 난이도 : 골드 4 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 전략 전형적인 DP 문제이다. i 번째 집을 j 색으로 칠하는 비용을 cost[i][j]라고 하자. 0번째 집 ~ i 번째 집을 칠할 때 i번째 집을 j 색으로 칠했을 때 최소 비용을 다음과 같은 점화식으로 표현할 수 있다. dp[i][j] = cost[i][j] + min( {dp[i - 1][j가 아닌 색] } )..

BOJ 14238 출근 기록 난이도 : 골드 3 https://www.acmicpc.net/problem/14238 14238번: 출근 기록 스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 www.acmicpc.net 전략 S의 길이가 최대 50이므로, 모든 경우의 수를 다 탐색하면 안된다. 메모이제이션을 사용해서 중복된 연산을 제거해야 한다. 불가능한 것이 계산된 (방문된) 상태는 bool 타입의 dp 배열을 통해 검사하여 제거할 수 있다. 경우의 수 탐색은 재귀 호출로 구현된 dfs로 이루어진다. 시행착오 처음에는 dp의 기준을 dp[현재 idx]..

BOJ 12969 ABC 난이도 : 골드 1 https://www.acmicpc.net/problem/12969 12969번: ABC 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다. www.acmicpc.net 전략 'A'의 개수 a, 'B'의 개수 b로 이루어진 길이가 len인 문자열에서 조건을 만족하는 쌍이 pair만큼 있다면 len + 1 길이의 문자열에서의 pair은 다음과 같다. 1. 'A' 선택 : pair 2. 'B' 선택 : pair + a 3. 'C' 선택 : pair + a + b 이전 길이의 문자열에서의 'A', 'B', 'C'의 위치와 관계 없이 개수 a, b에 따라..

BOJ 11066 파일 합치기 난이도 : 골드 3 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 전략 행렬 곱셈 순서 문제와 비슷한 유형이다. i ~ j까지의 파일을 합치는 최소 비용을 dp[i][j]로 하여 갱신시켜야 한다. 구하고자 하는 목표는 dp[1][K] 이므로 작은 문제부터 차근차근 올라오면 풀 수 있다. a ~ b 파일의 크기 합이 sum(a, b)라면 dp[i][j]는 다음과 같이 유도할 수 있다. dp[i][i] = ..

BOJ 12869 뮤탈리스크 난이도 : 골드 4 https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 전략 처음에는 hp가 많이 남은 순으로 9, 3, 1을 배정해서 그리디로 풀 수 있을까 고민했다. 하지만 12, 9, 3 같은 경우를 생각해보면 12, 9, 3 -> 3, 6, 2 -> 0, 0, 1 -> 0, 0, 0 으로 3번이 되는데 최적의 방법은 12, 9, 3 -> 9, 0, 2 -> 0, 0, 0 으로 2번만에 가능한 것을 볼수 있다. 즉 경우의 ..

BOJ 10422 괄호 난이도 : 골드 3 https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net 전략 길이 L에 대해서 올바른 괄호 문자열이 되려면 '(' 이 L/2, ')' 이 L/2 개 있어야 한다. 그렇다면 L/2 개의 ( 위치만 정해주면 되는데 단순히 공식화시키기는 어려워보인다. 열린 괄호 > 닫힌 괄호 또는 닫힌 괄호 > 열린 괄호 인 배치가 제한되므로 경우를 직접 확인해야 하기 때문이다. L은 최대 5000이므로 각 경우의 수를 탐색한다..

BOJ 7579 앱 난이도 : 골드 3 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 전략 냅색 문제랑 비슷한 유형이라서 우선 메모리 크기를 살펴본다. m_i 는 최대 10,000,000인 정수이며 N이 최대 100이므로 메모리 크기에 대해 dp 배열을 생성하면 GB 단위의 메모리를 사용하게 되므로 불가능하다. c_i 는 최대 100이므로 교체 비용을 기준으로 dp를 진행해야 한다. dp를 2차원 배열로 표현하여 [1, i] 범위의 앱까지 탐색했을 ..

BOJ 1005 ACM Craft 난이도 : 골드 3 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 전략 단순 위상정렬해서 순서만 중요한 것이 아니라 소요시간을 계산해야 한다. 이는 다음 노드 탐색 과정에서 메모이제이션을 이용하여 최댓값을 저장하는 방식을 사용했다. 단순히 값을 저장하면 되는 것처럼 보이지만, 여러 경로가 합쳐질 때는 최댓값을 이용하여야 결과를 얻을 수 있다. 시행착오 메모이제이션을 큐에서 꺼낸 위치에서 실행했는데, 이미..