단어 퍼즐은 주어진 단어 조각들을 이용해서 주어진 문장을 완성하는 퍼즐입니다. 이때, 주어진 각 단어 조각들은 각각 무한개씩 있다고 가정합니다. 예를 들어 주어진 단어 조각이 [“ba”, “na”, “n”, “a”]인 경우 "ba", "na", "n", "a" 단어 조각이 각각 무한개씩 있습니다. 이때, 만들어야 하는 문장이 “banana”라면 “ba”, “na”, “n”, “a”의 4개를 사용하여 문장을 완성할 수 있지만, “ba”, “na”, “na”의 3개만을 사용해도 “banana”를 완성할 수 있습니다. 사용 가능한 단어 조각들을 담고 있는 배열 strs와 완성해야 하는 문자열 t가 매개변수로 주어질 때, 주어진 문장을 완성하기 위해 사용해야 하는 단어조각 개수의 최솟값을 return 하도록 solution 함수를 완성해 주세요. 만약 주어진 문장을 완성하는 것이 불가능하면 -1을 return 하세요.
제한사항
strs는 사용 가능한 단어 조각들이 들어있는 배열로, 길이는 1 이상 100 이하입니다.
strs의 각 원소는 사용 가능한 단어조각들이 중복 없이 들어있습니다.
사용 가능한 단어 조각들은 문자열 형태이며, 모든 단어 조각의 길이는 1 이상 5 이하입니다.
t는 완성해야 하는 문자열이며 길이는 1 이상 20,000 이하입니다.
모든 문자열은 알파벳 소문자로만 이루어져 있습니다.
입출력 예
strstresult
["ba","na","n","a"]
"banana"
3
["app","ap","p","l","e","ple","pp"]
"apple"
2
["ba","an","nan","ban","n"]
"banana"
-1
입출력 예 설명
입출력 예 #1 문제의 예시와 같습니다.
입출력 예 #2 "ap" 1개, "ple" 1개의 총 2개로 "apple"을 만들 수 있으므로 필요한 단어 개수의 최솟값은 2를 return 합니다.
입출력 예 #3 주어진 단어로는 "banana"를 만들 수 없으므로 -1을 return 합니다.
접근 방법
단어의 0번째 문자부터 끝까지 최소한의 갯수로 만들어 나가는 dp테이블을 채워가며 해결 할 수 있는 문제입니다.
예를들어
[b][a][n][a][n][a]가 있다면
[b]를 최소한으로 만들 수 있는 횟수
[ba]를 최소한으로 만들 수 있는 횟수
[ban]를 최소한으로 만들 수 있는 횟수
.........
[banana]를 최소한으로 만들 수 있는 횟수를 채워가면 됩니다.
저와 같은 경우는 Top Down방식을 사용하였고
dp[i] = (i번째부터 단어의 마지막까지 문자열을 만드는 최소 횟수)를 의미합니다.
단어를 만들어감에 있어서 길이가 긴 단어를 우선적으로 채워 만드는 것이 유리합니다.
strs[]를 긴 단어부터 정렬을 한 뒤, for문으로 탐색을 하였습니다.
자세한 내용은 소스 코드에 주석 처리하겠습니다.
소스 코드
class Solution {
String t;
String[] strs;
int dp[];
//문자열의 길이 순 정렬
Comparator<String> c = new Comparator<String>() {
public int compare(String s1, String s2) {
return Integer.compare(s2.length(), s1.length());
}
};
public int solve(int idx){
//dp[i]는 i~마지막 문자열을 채울 수 있는 최소 횟수를 의미
//더 이상 진행 불가능
if(idx == t.length())
return 0;
if(dp[idx] != -1)
return dp[idx];
// 최소값을 찾아야 하므로 충분히 큰 값으로 초기화
dp[idx] = 20001;
for(int i=0;i<strs.length;i++){
// (현재까지 만들어진 문자열의 길이 + 새로운 퍼즐의 크기)가
// 단어의 길이보다 짧아야 함
if(idx + strs[i].length() <= t.length()){
boolean flag = true;
// substring으로 잘라서 문자열을 비교할경우 시간초과가 납니다. ㅠㅠ
// 채워나갈 수 있는 단어인지 검사
for(int j = 0; j < strs[i].length(); j++) {
if(t.charAt(idx + j) != strs[i].charAt(j)) {
flag = false;
break;
}
}
if(flag)
dp[idx] = Math.min(dp[idx], solve(idx + strs[i].length()) + 1);
}
}
return dp[idx];
}
public int solution(String[] strs, String t) {
dp = new int[t.length()];
Arrays.fill(dp, -1);
Arrays.sort(strs, c);
this.strs = strs; this.t = t;
int answer = solve(0);
return answer = (answer <= 20000) ? answer : -1;
}
}
사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다. 예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집니다.
((1 - 5) - 3) = -7
(1 - (5 - 3)) = -1
위 예시와 같이 뺄셈은 연산 순서에 따라 그 결과가 바뀔 수 있습니다. 또 다른 예로 식 1 - 3 + 5 - 8은 연산 순서에 따라 다음과 같이 5가지 결과가 나옵니다.
(((1 - 3) + 5) - 8) = -5
((1 - (3 + 5)) - 8) = -15
(1 - ((3 + 5) - 8)) = 1
(1 - (3 + (5 - 8))) = 1
((1 - 3) + (5 - 8)) = -5
위와 같이 서로 다른 연산 순서의 계산 결과는[-15, -5, -5, 1, 1]이 되며, 이중 최댓값은 1입니다. 문자열 형태의 숫자와, 더하기 기호("+"), 뺄셈 기호("-")가 들어있는 배열 arr가 매개변수로 주어질 때, 서로 다른 연산순서의 계산 결과 중 최댓값을 return 하도록 solution 함수를 완성해 주세요.
제한 사항
arr는 두 연산자 "+", "-" 와 숫자가 들어있는 배열이며, 길이는 3 이상 201 이하 입니다.
arr의 길이는 항상 홀수입니다.
arr에 들어있는 숫자의 개수는 2개 이상 101개 이하이며, 연산자의 개수는 (숫자의 개수) -1 입니다.
숫자는 1 이상 1,000 이하의 자연수가 문자열 형태로 들어있습니다.. (ex : "456")
배열의 첫 번째 원소와 마지막 원소는 반드시 숫자이며, 숫자와 연산자가 항상 번갈아가며 들어있습니다.
입출력 예
arrresult
["1", "-", "3", "+", "5", "-", "8"]
1
["5", "-", "3", "+", "1", "+", "2", "-", "4"]
3
입출력 예시
입출력 예 #1 위의 예시와 같이 (1-(3+(5-8))) = 1 입니다.
입출력 예 #2 (5-(3+((1+2)-4))) = 3 입니다.
접근 방법
개인적으로 굉장히 재미있게 풀었던 문제입니다.
문제를 해결하기 위해서는 부분문제를 해결하며 전체의 최적해를 찾아가는 동적 계획법을 사용할 수 있습니다.
1. [A1 ~ An] + [B1 ~ Bn] 의 최대값을 구하기 위해서는 [A1 ~ An]이 최대가 되어야하고 [B1 ~ Bn]이 최대가 되어야 할 것입니다.
2. [A1 ~ An] - [B1 ~ Bn] 의 최대값을 구하기 위해서는 [A1 ~ An]이 최대가 되어야하고 [B1 ~ Bn]이 최소가 되어야 할 것입니다.
3. [A1 ~ An] = [A1 ~ Ax] + [Ax+1 ~ An]또는 [A1 ~ Ax] - [Ax+1 ~ An] 표현할 수 있습니다. 즉 부분 문제부터 해결하며 최적해를 구합니다. 이 때 중복되는 연산을 없애기 위해 dp테이블을 구성합니다.
4. dp테이블은 3차원으로 구성할 수 있습니다.
dp[최대 or 최소][범위의 시작][범위의 끝] = 범위의 최대 혹은 최소 값
dp테이블의 1차원은 0또는 1로써 최대값을 저장하는 테이블인지 최소값을 저장하는 테이블인지 지정하며 그에 따른 값을 dp테이블에 기록합니다.
ex1) dp[0][3][7] -> 3번째 숫자부터 7번째 숫자까지의 최대값
ex2) dp[1][2][7] -> 2번째 숫자부터 7번째 숫자까지의 최소값
자세한 내용은 아래 소스코드에 주석처리 하였습니다.
소스 코드
class Solution {
//dp의 1차원의 0은 최대 테이블, 1은 최소테이블
int dp[][][] = new int[2][200][200];
char oper[]; int nums[]; //oper는 연산자를 기록, nums는 숫자를 기록
String arr[];
int tmp = 987654321;
//dp테이블 초기화
public void init(){
int n = arr.length/2;
for(int i=0;i<n+1;i++)
for(int j=0;j<n+1;j++){
dp[0][i][j] = -1 * tmp;
dp[1][i][j] = tmp;
}
nums = new int[n + 1];
oper = new char[n];
//arr의 짝수 idx는 숫자가 기록, 홀수 idx에는 연산자가 기록되어 있음
for(int i=0;i<arr.length;i++){
if(i%2 == 0) nums[i/2] = Integer.parseInt(arr[i]);
else oper[i/2] = arr[i].charAt(0);
}
}
//flag == 0이면 최대, 1이면 최소
public int solve(int flag, int start, int end){
// 범위가 숫자 하나로 일치하는 경우
if(start == end)
return dp[flag][start][end] = nums[start];
//이미 해결했던 문제라면
if(flag == 0 && dp[flag][start][end] != -1*tmp)
return dp[flag][start][end];
if(flag == 1 && dp[flag][start][end] != tmp)
return dp[flag][start][end];
// flag에 따라 초기값을 다르게 줌
int ret = (flag == 0) ? -1 * tmp : tmp;
// 방문 체크
dp[flag][start][end] = 0;
if(flag == 0){
//최대를 구해야 하는 경우
for(int mid = start; mid < end; mid++){
if(oper[mid] == '-') //두 구간 사이의 연산자가 "-"일때, 최대 - 최소
ret = Math.max(ret, solve(0, start, mid) - solve(1, mid+1, end));
else //두 구간 사이의 연산자가 "+"일때, 최대 + 최대
ret = Math.max(ret, solve(0, start, mid) + solve(0, mid+1, end));
}
}
else{
//최소를 구해야 하는 경우
for(int mid = start; mid < end; mid++){
if(oper[mid] == '-') //두 구간 사이의 연산자가 "-"일때, 최소 - 최대
ret = Math.min(ret, solve(1, start, mid) - solve(0, mid+1, end));
else //두 구간 사이의 연산자가 "+"일때, 최소 + 최소
ret = Math.min(ret, solve(1, start, mid) + solve(1, mid+1, end));
}
}
return dp[flag][start][end] = ret;
}
public int solution(String arr[]) {
int answer = -1;
this.arr = arr;
init();
// solve(처음부터 마지막의 최대값), flag = 0, start = 0, end = 마지막 idx
return answer = solve(0, 0, arr.length/2);
}
}
카카오 택시 개발자 Jay-G는 다음 업데이트를 준비하기 위해 개선사항을 위한 여러 피드백을 받았다. 그중에서 손님이 자주 탑승하는 위치를 추천해주었으면 한다는 의견이 많았다.
다음 업데이트 준비를 위해 Jay-G는 택시의 승하차 및 이동 경로를 수집하여 분석하기 시작하였다. 데이터를 분석하던 Jay-G는 몇 가지 특이사항을 발견했다. 택시의 이동 경로를 GPS를 통해 수집하게 되는데, GPS 신호 불량, 통신 오류 등 다양한 원인으로 위치의 오류가 발생한 것을 알게 되었다. 다만 승차 위치와 하차 위치는 오류가 없는 것으로 확인이 되었다.
개발자 Jay-G는 수집한 이동 경로의 오류를 최소한으로 수정하여 좀 더 정확한 이동 경로를 구하고 싶어 한다.
택시는 다음과 같은 조건으로만 이동한다. 먼저 택시는 거점을 이동해 다니며, 거점 간의 이동은 해당하는 도로가 있는 경우에만 가능하다. 또한, 교통 상황에 따라 택시는 한 거점에 머무를 수 있고, 왔던 길을 되돌아갈 수 있다. 모든 도로는 방향이 별도로 없는 왕복 도로이다.
예를 들어, 위 그래프에서 택시가 다음과 같이 시간대별로 이동 경로를 보내왔다.
t위치
1
1
2
2
3
3
4
3
5
6
6
7
하지만 위의 택시가 보내온 경로에는거점 3에서거점 6으로 이동할 수 있는 도로가 없으므로 이동 경로에 오류가 있다.
이러한 오류를 최소한으로 수정하여 이동 가능한 경로로 만들고 싶다. 이 경우 1회의 오류를 수정하여 다음과 같이 이동 가능한 경로를 만들 수 있다. 시간t=4의 위치를거점 5로 한 번 수정하면 이동 가능한 경로가 된다.
t위치
1
1
2
2
3
3
4
5
5
6
6
7
이와 비슷하게 시간t=4의 위치를거점 4로 바꾸거나, 시간t=5위치를거점 5로 바꾸면 이동 가능한 경로로 만들 수 있다. 위의 경우 수정한 오류의 개수는 1개이다.
t위치
1
1
2
2
3
3
4
4
5
6
6
7
t위치
1
1
2
2
3
3
4
3
5
5
6
7
위와 같이 택시가 보내온 경로에서 이동 가능한 경로로 만드는 최소의 오류 수정 횟수를 구하여라.
입력 형식
주어지는 입력은 총 다섯 가지로, 거점 개수n과 도로의 개수m, 각 거점 간의 연결된 도로 정보edge_list, 택시가 시간대별로 보내오는 거점 정보의 총 개수k, 그리고 머물렀던 거점의 정보gps_log이다. 제한조건은 아래와 같다.
2 <= n <= 200
1 <= m <= 10,000
2 <= k <= 100
edge_list는m × 2크기의 2차원 배열로, 각 행의 두 값은 도로가 잇는 두 거점의 번호를 의미한다.
거점의 번호는 1부터 n까지 숫자이다.
모든 도로는 양방향 통행이 가능하다.
입력되는 데이터에서 항상 모든 거점 간 경로가 있음이 보장되지 않는다.
gps_log의 시작 거점과 도착 거점은 바뀔 수 없다.
출력 형식
이동 가능한 경로로 만들 수 있는 최소의 오류 수정 횟수를 리턴한다. 올바른 경로로 수정하는 것이 불가능할 경우-1을 리턴한다.
두 예제 모두edge_list의 데이터는 본문의 그림과 같은 예이다. 첫 번째 테스트 케이스에서gps_log로 주어진 경로 중거점 3에서거점 6으로 가는 도로가 없다. 여기서 시간t=4의 위치를거점 5로 한 번 수정하면 이동 가능한 경로가 된다. 두 번째 테스트 케이스는gps_log로 주어진 경로가 모두 도로로 연결된 경우이므로 수정이 필요 없다.
접근 방법
DP를 사용해 해결하였습니다.
저는 동적계획법을 사용할 때 재귀함수를 사용한 Top-Down방식을 선호하기 때문에 Top-Down방식으로 해결하였습니다.
dp테이블의 설계는 아래와 같습니다.
dp[시간][지점] = 최적해(마지막 시간 부터 현재 시간까지의 거점들을 이동 가능 경로로 만들 수 있는 최소 변경 횟수)
문제를 해결하기에 앞서 필요한 데이터를 전처리 해야 합니다. 저는 아래와 같은 구조로 데이터를 전처리 하였습니다.
ArrayList <ArrayList<Integer>> info = new ArrayList();
info[현재위치] = {현재 위치로 부터 갈 수 있는 거점들의 집합}
info의 초기화 코드는 아래와 같습니다.
public void init(int n, int[][] edge_list, int[] gps_log){
this.gps_log = gps_log;
//dp를 -1로 초기화
for(int i=0;i<=gps_log.length;i++)
Arrays.fill(dp[i], -1);
for(int i=0;i<=n;i++){
info.add(new ArrayList<Integer>());
info.get(i).add(i); //정차하는 경우
}
for(int i=0;i<edge_list.length;i++){
info.get(edge_list[i][0]).add(edge_list[i][1]); //양 방향
info.get(edge_list[i][1]).add(edge_list[i][0]); //양 방향
}
}
dp의 핵심 풀이는 info[현 위치]의 한 요소를 next라고 할 때 가능한 모든 next에 대해 최소를 구해가는 것이고,
next == gps_log[현재 시간 + 1]라면 거점 정보의 변경 없음, next != gps_log[현재 시간 + 1]라면 변경횟수 1회 증가를 하여 반환을 하면 됩니다. 자세한 설명은 소스 코드에 주석 처리 하겠습니다.
여기서 중요한 점은 불가능한 경우가 2가지가 있다는 점입니다.
1. edge_list에서 마지막 거점으로 가능 경로가 없는 경우
2. 마지막 거점을 변경해야지만 조건에 만족하는 경우
소스 코드
import java.util.*;
class Solution {
ArrayList <ArrayList<Integer>> info = new ArrayList();
int[] gps_log;
int[][] dp = new int[101][201];
int MAX = 54321;
public void init(int n, int[][] edge_list, int[] gps_log){
this.gps_log = gps_log;
for(int i=0;i<=gps_log.length;i++)
Arrays.fill(dp[i], -1);
for(int i=0;i<=n;i++){
info.add(new ArrayList<Integer>());
info.get(i).add(i); //정차하는 경우
}
for(int i=0;i<edge_list.length;i++){
info.get(edge_list[i][0]).add(edge_list[i][1]); //양 방향
info.get(edge_list[i][1]).add(edge_list[i][0]); //양 방향
}
}
public int solve(int time, int now){
// 마지막 지점은 변경 불가능 이므로 1이 아닌 MAX를 return
if(time == gps_log.length - 1)
return dp[time][now] = (gps_log[time] == now) ? 0 : MAX;
//이미 구해진 최적해가 있다면
if(dp[time][now] != -1)
return dp[time][now];
//ret는 최소를 구하기 위한 변수이므로 비교적 큰 값으로 초기화
int ret = MAX;
dp[time][now] = 0;
for(int i=0;i<info.get(now).size();i++){
int next = info.get(now).get(i);
ret = Math.min(solve(time+1, next), ret);
}
//변경해야 하는 경우 +1
return dp[time][now] = (gps_log[time] == now) ? ret : ret + 1;
}
public int solution(int n, int m, int[][] edge_list, int k, int[] gps_log) {
int answer = 0;
init(n, edge_list, gps_log);
answer = solve(0, gps_log[0]);
//마지막 지점으로 가는 경로가 없거나, 만족하는 해가 없다면
return answer = (dp[k-1][gps_log[k-1]] == -1 || dp[k-1][gps_log[k-1]] >= MAX) ? -1 : answer;
}
}
카카오내비 개발자인 제이지는 시내 중심가의 경로 탐색 알고리즘 개발 업무를 담당하고 있다. 최근 들어 보행자가 자유롭고 편리하게 걸을 수 있도록 보행자 중심의 교통 체계가 도입되면서 도심의 일부 구역은 자동차 통행이 금지되고, 일부 교차로에서는 보행자 안전을 위해 좌회전이나 우회전이 금지되기도 했다. 복잡해진 도로 환경으로 인해 기존의 경로 탐색 알고리즘을 보완해야 할 필요가 생겼다.
도시 중심가의 지도는m × n크기의 격자 모양 배열city_map으로 주어진다. 자동차는 오른쪽 또는 아래 방향으로 한 칸씩 이동 가능하다.
city_map[i][j]에는 도로의 상황을 나타내는 값이 저장되어 있다.
0인 경우에는 자동차가 자유롭게 지나갈 수 있다.
1인 경우에는 자동차 통행이 금지되어 지나갈 수 없다.
2인 경우는 보행자 안전을 위해 좌회전이나 우회전이 금지된다. (왼쪽에서 오던 차는 오른쪽으로만, 위에서 오던 차는 아래쪽으로만 진행 가능하다)
도시의 도로 상태가 입력으로 주어졌을 때, 왼쪽 위의 출발점에서 오른쪽 아래 도착점까지 자동차로 이동 가능한 전체 가능한 경로 수를 출력하는 프로그램을 작성하라. 이때 가능한 경로의 수는 컴퓨터가 표현할 수 있는 정수의 범위를 넘어설 수 있으므로, 가능한 경로 수를20170805로 나눈 나머지 값을 출력하라.
입력 형식
입력은 도시의 크기를 나타내는m과n, 그리고 지도를 나타내는 2차원 배열city_map으로 주어진다. 제한조건은 아래와 같다.
1 <= m, n <= 500
city_map의 크기는m × n이다.
배열의 모든 원소의 값은0,1,2중 하나이다.
출발점의 좌표는(0, 0), 도착점의 좌표는(m - 1, n - 1)이다.
출발점과 도착점의city_map[i][j]값은0이다.
출력 형식
출발점에서 도착점까지 이동 가능한 전체 경로의 수를20170805로 나눈 나머지를 리턴한다.
첫 번째 예제는 모든 도로가 제한 없이 통행 가능한 경우로, 가능한 경우의 수는 6가지이다. 두 번째 예제는 문제 설명에 있는 그림의 경우이다. 가능한 경우의 수는 빨간 실선과 노란 점선 2가지뿐이다.
접근 방법
동적계획법으로 해결할 수 있는 문제였습니다. 동적계획법은 dp[x좌표][y좌표][현재방향]으로 설계할 수 있으며 현재방향에 대한 차원이 필요한 이유는 만약 어떤 지점의 값이 2일때 한 방향으로만 갈 수 있으므로 현재 어떤 방향을 가지고 있는가에 따라 다른 경우의 수가 되기 때문입니다.
자세한 내용은 코드에 주석을 달아놓겠습니다.
소스 코드
#include <vector>
#include <string.h>
using namespace std;
int MOD = 20170805;
int dp[501][501][2]; //마지막 차원은 현재 방향
pair<int, int> nextdir[2] = {{1,0},{0,1}}; //오른쪽 또는 아래로만 이동 가능
vector<vector<int>> map;
int M, N;
bool inRange(int x, int y){
return (0 <= x && x < M && 0 <= y && y < N);
}
int solve(int x, int y, int dir){
int &ref = dp[x][y][dir];
//방문한 적 있다면
if(ref != -1)
return ref;
//목표지점에 도달했다면
if(x == M - 1 && y == N - 1)
return ref = 1;
//방문 표시
ref = 0;
//2방향 모두 가능
if(map[x][y] != 2){
//2방향에 대한 반복문
for(int i=0;i<2;i++){
int next_x = x + nextdir[i].first;
int next_y = y + nextdir[i].second;
//다음 좌표가 범위를 벗어나지 않으며 통행 불가 지역이 아닌 경우
if(inRange(next_x, next_y) && map[next_x][next_y] != 1)
ref += solve(next_x, next_y, i) % MOD;
}
}
else{ //회전 불가능, map[x][y] == 2인 경우
//현재 진행 방향이 dir이며 dir로만 진행 가능
int next_x = x + nextdir[dir].first;
int next_y = y + nextdir[dir].second;
if(inRange(next_x, next_y) && map[next_x][next_y] != 1)
ref += solve(next_x, next_y, dir) % MOD;
}
return ref %= MOD;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
int answer = 0;
memset(dp, -1, sizeof(dp));
//전역 변수로 초기화
M = m; N = n; map = city_map;
return answer = solve(0, 0, 0);
}
유통전문회사카카오상사의 오너인제이지는 새로운 사업 아이템을 구상하기 위해 전문경영인(CEO)인프로도에게 회사의 경영을 부탁하였습니다. 카카오상사는 직원들을 여러 개의 팀 단위로 조직을 구성하고 있으며 아래 그림은 CEO를 포함하여 10명의 직원과 4개의 팀으로 구성되어 있는 회사 조직도를 보여주고 있습니다.
그림의 조직도는 다음과 같이 설명할 수 있습니다.
그림의 각 원들은 각각의 직원 1명을 표시하고 있으며, CEO를 포함하여 총 10명의 직원을 표시하고 있습니다.
원 안에 적힌 두 개의 숫자는 직원의 정보를 담고 있습니다. 왼쪽 숫자는직원번호이며 직원을 식별할 수 있도록 1번부터 순서대로 발급되는 일련번호이며, 오른쪽 숫자는해당 직원의 하루평균 매출액을 나타냅니다. 위 그림에서1번직원은 14원을,9번직원은 28원의 하루평균 매출액을 기록하고 있습니다.
CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 쪽의 직원은 팀원을 의미합니다. 3-1. 직원번호1번은 회사의 CEO로 고정되어 있으며, CEO는 항상 팀장이고 팀원일 수 없어 화살표를 받는 쪽이 될 수 없습니다. 3-2. 반면에 CEO를 제외한 나머지 모든 직원들은 다른 누군가로부터 정확히 1개의 화살표를 받게 됩니다. 3-3. 한 직원은 최대 2개의 팀에 소속될 수 있습니다. 만약 어떤 직원이 두 개의 팀에 소속되어 있다면, 반드시 하나의 팀에서는 팀장, 나머지 팀에서는 팀원이어야 합니다. 팀장을 겸임하거나, 두 개의 팀에서 팀원이 될 수는 없습니다. 예를들어10번직원은D팀의 팀장이면서 동시에5번직원이 팀장으로 있는C팀에 속한 팀원입니다. 3-4.5번, 9번, 10번직원은 받는 쪽의 화살표와 시작하는 화살표가 모두 있으므로 팀장인 동시에 팀원입니다. 3-5.2번, 3번, 4번, 6번, 7번, 8번직원은 시작하는 화살표가 없고 받는 쪽의 화살표만 있으므로 팀장이 아니며 오직 팀원입니다. 3-6.1번직원인 CEO는 받는 쪽의 화살표가 없고 시작하는 화살표만 있으며 항상 팀원이 아닌 팀장입니다. 3-7. 그림의 조직도에는A, B, C, D총 4개의 팀이 존재하며, 각각1번, 9번, 5번, 10번직원이 팀장 직위를 담당하게 됩니다.
제이지는 자신이 구상한 새로운 사업 아이템에 대해 직원들에게 설명하고자 하루 일정으로 워크숍을 계획하고 있습니다. 단, 모든 직원을 참석시킬 수 없어 아래와 같은 기준으로 워크숍에 참석할 직원들을 선발하려고 합니다.
워크숍에서 교육받은 내용은 전 직원들에게 공유되어야 하므로모든 팀은 최소 1명 이상의 직원을 워크숍에 참석시켜야 합니다.
워크숍 기간 동안, 회사의 매출 손실을 최소화하는 것이 중요하므로 워크숍에 참석하는 직원들의 하루평균 매출액의 합이 최소가 되어야 합니다.
위 그림의 조직도에서 회색으로 색칠된1번, 7번, 10번직원을 워크숍에 참석시키면 모든 팀에서 최소 한 명 이상의 직원을 참석시킨 것이 되며, 해당 직원들의 하루평균 매출액의 합은44(14+13+17)원입니다.10번 직원은 C팀과 D팀 모두에 속해 있으므로, 두 팀에서 모두 참석한 것으로 인정됩니다.
[문제]
직원들의 하루평균 매출액 값을 담은 배열 sales, 직원들의팀장-팀원의 관계를 나타내는 2차원 배열 links가 매개변수로 주어집니다. 이때, 모든 팀에서 최소 한 명 이상 워크숍에 참석하면서, 참석하는 직원들의 하루평균 매출액의 합을 최소로 하려고 합니다. 그렇게 최소화된 매출액의 합을 구해서 return 하도록 solution 함수를 완성해 주세요.
[제한사항]
sales 배열의 크기는 2 이상 300,000 이하입니다. sales 배열의 크기는 CEO를 포함한 전체 직원 수와 같습니다.
sales 배열은 각 직원들의 하루평균 매출액을 담고 있으며,1번직원부터 직원번호 순서대로 주어집니다.
sales 배열의 각 원소의 값은 0 이상 10,000 이하인 정수입니다.
links 배열의 크기는sales 배열의 크기 - 1입니다. 즉, 전체 직원 수보다 1이 작습니다.
links 배열의 각 원소는 [a, b] 형식입니다.
a는 팀장의 직원번호, b는 a팀장이 관리하는 팀원의 직원번호이며, a와 b는 서로 다른 자연수입니다.
입출력 예 #2 직원번호가 2인 직원 한 명을 워크숍에 참석시키는 것이 최선이며, 2번 직원의 하루평균 매출액은 6원입니다. 따라서 6을 return 해주어야 합니다.
입출력 예 #3 직원번호가 4, 5인 직원 두 명을 워크숍에 참석시키는 것이 최선이며, 4번, 5번 직원의 하루평균 매출액의 합은 5(1+4)원 입니다. 따라서 5를 return 해주어야 합니다.
입출력 예 #4 직원번호가 3, 4인 직원 두 명을 워크숍에 참석시키는 것이 최선이며, 3번, 4번 직원의 하루평균 매출액의 합은 2(1+1)원 입니다. 따라서 2를 return 해주어야 합니다.
접근 방법
트리 DP를 사용하여 해결할 수 있는 문제였습니다.
일반적으로 트리 DP는 2개의 차원을 가지며
DP[노드 번호][노드 포함 여부] = 최적해
의 구조를 가지고 있습니다.
문제의 풀이는 다음과 같습니다.
1. 문제에서 주어진 vector<vector<int>> links를 통해 트리를 구성한다.
links는 명확하게 부모노드에서 자식노드로 연결되는 순서를 가진 단방향의 구조입니다.
또한 문제에서 1이 최상위 노드라고 알려주었기 때문에 트리를 구성하는 것은 vector를 사용한 인접리스트로 구성을 할 수 있습니다.
void makeTree(vector<vector<int>> &links){
for(int i=0; i<links.size(); i++){
int from = links[i][0];
int to = links[i][1];
tree[from].push_back(to);
}
}
2. 문제의 조건에 따라 DP를 채워나간다.
DP 테이블을 채워나갈 때 크게 2가지 경우로 나눌 수 있습니다.
1. 자신이 포함되어 있을 때 (include == true)
2. 자신이 포함되지 않았을 때 (include == false)
1. 자신이 포함되어 있을 때 (include == true)
1번 경우에서 처리 과정은 트리 DP를 한번이라도 다뤄봤다면 어렵지 않게 생각해 낼 수 있었을 것입니다.
자신이 포함이 되어있다면 그룹 내에서 최소 한명이 포함이 되어있기 때문에 자식 노드는 포함을 시켜도 되고 안 시켜도 됩니다. 이 때 자식 노드의 번호 K에 대해 K를 포함시키는 것이 좋은지, K를 포함시키지 않는 것이 좋은지 생각하여야 합니다.
즉 자식노드를 포함시키는 경우 dp[k][1]와 자식노드를 포함시키지 않는 경우 dp[k][0] 중 더 작은 값을 결정해야 합니다. 작은 값을 결정해야 하는 이유는 값이 작을 수록 매출액의 손해를 줄여줄 수 있기 때문이고 이것이 최적해를 만족하기 때문입니다.
//int &ref = dp[now][1];
if(include){ //나를 포함했다면, 하위 직원을 포함해도 되고 안해도 됨
long long ans = 0;
for(int i=0;i<tree[now].size();i++){
int next = tree[now][i];
ans += min(solve(next, true), solve(next, false));
}
return ref = ans + salesInfo[now - 1];
}
2. 자신이 포함되지 않았을 때 (include == false)
이 경우에 대해 풀이를 생각하는 것은 쉽지 않았습니다.
1번 경우와 마찬가지로 자식노드 k에 대해 dp[k][1]과 dp[k][0] 중 더 작은 값 만을 포함을 해야 합니다. 이 때 모든 자식노드가 참여를 하지 않는 것이 최적해 일 때 강제로 1명은 참여를 시켜야 합니다. 그렇다면 어떤 자식 노드를 참여 시킬지 결정을 해야 합니다.
결정을 하는 방법은 한 자식노드가 자신이 참여를 했을 때와 안 했을 때의 차이가 가장 적은 것이 가장 좋습니다. 차이가 가장 적은 것이 좋은 이유는 이런 상황에서는 기본적으로 모든 k에 대해 dp[k][1] > dp[k][0]일 것입니다. 즉 참여를 하는 것이 값이 크기 때문에 좋지 않은 상황이며, dp[k][1]와 dp[k][0]의 차이가 작을수록 참여를 했을 때 불참을 했을 때 보다 회사의 손실이 작아지기 때문입니다. (이 내용이 정확한 이해가 가지 않는다면 댓글 남겨주세요.)
else{ //내가 포함되지 않았다면 하위 직원 중 한 명 이상은 무조건 포함이 되어야함
long long ans = 0;
long long diff = (tree[now].size() > 0) ? 0x7FFFFFFF : 0;
bool flag = false; //모두가 불참여 한 것인지 확인 하기 위한 변수
for(int i=0;i<tree[now].size();i++){
int next = tree[now][i];
long long case1 = solve(next, true);
long long case2 = solve(next, false);
//참여 케이스의 값이 작다는 것은, 참여를 했다는 것이다.
if(case1 < case2) flag = true;
else diff = min(diff, case1 - case2);
ans += min(case1, case2);
}
//모든 자식 노드가 불참인 경우, 최소 한명은 참여를 시켜야함
return ref = (!flag) ? ans + diff : ans;
}
소스 코드
C++
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
vector<int> tree[300001];
long long dp[300001][2];
vector<int> salesInfo;
void makeTree(vector<vector<int>> &links){
for(int i=0; i<links.size(); i++){
int from = links[i][0];
int to = links[i][1];
tree[from].push_back(to);
}
}
long long solve(int now, bool include){
long long &ref = dp[now][include];
if (ref != -1)
return ref;
ref = 0;
if(include){ //나를 포함했다면, 하위 직원을 포함해도 되고 안해도 됨
long long ans = 0;
for(int i=0;i<tree[now].size();i++){
int next = tree[now][i];
ans += min(solve(next, true), solve(next, false));
}
return ref = ans + salesInfo[now - 1];
}
else{ //내가 포함되지 않았다면 하위 직원 중 한 명 이상은 무조건 포함이 되어야함
long long ans = 0;
long long diff = (tree[now].size() > 0) ? 0x7FFFFFFF : 0;
bool flag = false;
for(int i=0;i<tree[now].size();i++){
int next = tree[now][i];
long long case1 = solve(next, true);
long long case2 = solve(next, false);
//참여 케이스의 값이 작다는 것은, 참여를 했다는 것이다.
if(case1 < case2) flag = true;
else diff = min(diff, case1 - case2);
ans += min(case1, case2);
}
//모든 자식 노드가 불참인 경우, 최소 한명은 참여를 시켜야함
return ref = (!flag) ? ans + diff : ans;
}
}
long long solution(vector<int> sales, vector<vector<int>> links) {
long long answer = 0;
salesInfo = sales;
makeTree(links);
memset(dp, -1, sizeof(dp));
return answer = min(solve(1, false), solve(1, true));
}
Java
import java.util.*;
class Solution {
int dp[][] = new int[300001][2];
ArrayList<ArrayList<Integer>> info = new ArrayList();
int salesInfo[];
public void init(int[][] links, int[] sales){
salesInfo = sales;
for(int i=0;i<=sales.length;i++)
info.add(new ArrayList<Integer>());
for(int i=0;i<links.length;i++)
info.get(links[i][0]).add(links[i][1]);
for(int i=0;i<=sales.length;i++)
dp[i][0] = dp[i][1] = -1;
}
public int solve(int now, int include){
if(dp[now][include] != -1)
return dp[now][include];
dp[now][include] = 0;
int ret = 0;
if(include == 1){
for(int i=0;i<info.get(now).size();i++){
int next = info.get(now).get(i);
ret += Math.min(solve(next, 1), solve(next, 0));
}
return dp[now][include] = (ret + salesInfo[now - 1]);
}
else{
boolean flag = false;
int diff = (info.get(now).size() > 0) ? 0x7FFFFFFF:0;
for(int i=0;i<info.get(now).size();i++){
int next = info.get(now).get(i);
int case1 = solve(next, 1);
int case2 = solve(next, 0);
if(case1 < case2) flag = true;
else diff = Math.min(case1 - case2, diff);
ret += Math.min(case1, case2);
}
return dp[now][include] = (flag == true) ? ret:ret + diff;
}
}
public int solution(int[] sales, int[][] links) {
int answer = 0;
init(links, sales);
return answer = Math.min(solve(1, 1), solve(1, 0));
}
}
이 문제는 내리막 길(현재보다 더 값이 작은 지점)으로만 따라 갔을 때, 목적지에 도착하는 길의 수를 구하는 문제이며, 문제를 보았을때 DFS를 사용하면 top-down방식으로 가능할 것이고, BFS를 사용하면 bottom-up방식이 가능하다. 필자는 DFS를 이용한 top-down방식으로 해결하였다.
(1) 변수
dp[i][j]는 i,j에서 출발하였을 때, 내리막 길을 따라 도착지에 도착하였을 경우에 대한 길의 수이며, 방문 여부로도 사용된다. 초기값을 0으로 사용하게 되면, 방문을 하였어도 도착지점까지 못 간다면 계속 0이기 때문에 방문여부를 확인하기 어렵기 때문에 초기값을 -1로 하였다.
(2) solve()
int &ret = dp[x][y];
if (ret != -1) return ret;
if (x == n && y == m) return ret = 1;
ret = 0;
함수가 호출되었을때, 가장 먼저 방문여부( if (ret != -1) )를 판단한다. 중복되는 연산을 피하기 위해서이다. 방문을 하였으면 해당 dp에 저장된 값을 return한다. 좀 더 자세히 설명을 하자면 어차피 현재 함수의 x,y에서 갈 수 있는 경로를 이미 다 탐색을 한 값이 dp[x][y]에 저장되어 있으므로 함수를 더 진행시킬 필요가 없다는 것이다.
그 다음 도착지점에 도착했다면( if (x == n && y == m) ), 도착한 경로에 대한 경우가 추가 되었으므로 1을 return한다.
위의 두가지 경우가 아니면 방문을 했다는 의미로 값을 0으로 바꿔준다.
for (int i = 0; i < 4; i++) {
int next_x = x + direction[i].first;
int next_y = y + direction[i].second;
if (1 <= next_x && next_x <= n && 1 <= next_y && next_y <= m)
if (map[next_x][next_y] < map[x][y])
ret += solve(next_x, next_y);
}
그 이후 현재좌표의 상하좌우 4방향에 대해 map에 포함되어 있는 범위 내에서, 값이 더 작은 곳으로 이동시키면 된다.
소스 코드
#include <iostream>
#include <string.h>
using namespace std;
int n, m;
int map[501][501];
int dp[501][501];
pair<int, int> direction[4] = { {1,0}, {0,1}, {-1,0}, {0,-1} };
int solve(int x, int y) {
int &ret = dp[x][y];
if (ret != -1) return ret;
if (x == n && y == m) return ret = 1;
ret = 0;
for (int i = 0; i < 4; i++) {
int next_x = x + direction[i].first;
int next_y = y + direction[i].second;
if (1 <= next_x && next_x <= n && 1 <= next_y && next_y <= m)
if (map[next_x][next_y] < map[x][y])
ret += solve(next_x, next_y);
}
return ret;
}
int main() {
ios_base::sync_with_stdio(NULL);
cin.tie(0);
cout.tie(0);
memset(dp, -1, sizeof(dp));
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> map[i][j];
cout << solve(1, 1);
}
동적계획법을 사용하여 풀이하였으며, 재귀함수를 이용한 top-down방식을 사용하였으며 크게 어렵지 않은 문제였다.
(1) 변수
dp[i]는 i번째 날부터 상담을 하기 시작하였을 때 가질 수 있는 최대의 비용이다.
(2) solve( )
함수 내에서 cur은 현재 날짜를 의미한다.
if (cur > n + 1)
return -1;
if (cur == n + 1)
return dp[cur] = v[cur].second; //딱 마지막 날이면 그값을 반환
첫번째 if문은 현재날짜가 퇴사일을 지나간 경우이고, 두번째 if문은 정확히 퇴사 날짜를 포함하여 현재 상담이 종료되는 경우이다. 이 두가지 조건이 아니라면 다음 상담을 잡을 수 있는 가능성이 존재한다는 것이다.
for (int i = cur + v[cur].first; i <= n + 1; i++) { //미팅이 시작 가능한 경우의 한에서
int ret = solve(i);
if (ret != -1)
dp[cur] = max(ret + v[cur].second, dp[cur]);
}
return dp[cur];
i는 현재 날짜로 부터 상담을 마친 이후 가능한 모든 다음 상담의 시작 날짜이다. 하지만 위 for문에서 (i > n+1), 즉 상담날짜의 시작시점이 퇴사일이 지난 이후라면 자연스럽게 무시가 될것이다. max( )에서 ret + v[cur].second는 현재의 상담에 대한 비용을 계속해서 더해나간 것이고, 메모되었던 dp[cur]와 비교를 하여 더 큰 값으로 갱신 할 것이다.
소스 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair <int, int>> v(20, {0,0});
int dp[17];
int n;
int solve(int cur) { //1
if (cur > n + 1)
return -1;
if (cur == n + 1)
return dp[cur] = v[cur].second; //딱 마지막 날이면 그값을 반환
else { //만약 next로 진입이 가능하다면
for (int i = cur + v[cur].first; i <= n + 1; i++) { //미팅이 시작 가능한 경우의 한에서
int ret = solve(i);
if (ret != -1)
dp[cur] = max(ret + v[cur].second, dp[cur]);
}
return dp[cur];
}
}
int main() {
cin >> n;
v[0] = {1,0};
for (int i = 1; i <= n; i++) {
int t, p;
cin >> t >> p;
v[i] = { t,p };
}
cout << solve(0) << endl;
}
