오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.
BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.
N=4이고, S가 아래와 같은 경우를 살펴보자.
i\j
1
2
3
4
1
1
2
3
2
4
5
6
3
7
1
2
4
3
4
5
예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.
스타트 팀: S12 + S21 = 1 + 4 = 5
링크 팀: S34 + S43 = 2 + 5 = 7
1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.
스타트 팀: S13 + S31 = 2 + 7 = 9
링크 팀: S24 + S42 = 6 + 4 = 10
축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.
풀이
모든 경우의 수를 돌면서 최소 차이의 경우를 찾아내면 되는 문제
문제는 어떻게 구현할 것이냐인데 나도 이런 문제에서 모든 경우의 수를 어떻게 구하지? 하는 생각에
풀지 못하고 코드를 참조했었는데 지금와서는 모든 경우의 수를 구한다 -> 백트래킹, DFS, 비트마스킹을 사용하면 어느정도 해소된다 생각한다.
어쨌건 풀이자체는 간단하다 백트래킹으로 모든 경우의 수에서 visit이면 start, !visit이면 link팀으로 생각하고
이 때 차이를 계산하고 차이가 적은 점수로 갱신해주면 된다.
풀이는 간단하지만 구현상에서 언제 visit을 false로 할 것인가 라던가 조금 섬세함이 필요한 문제
public class Main { static int MAX = 21; static int arr[][]; static boolean visit[]; static int N = 0; static int ans = 987654321;
static int getScore(int array[]) { int result = 0; int len = N/2; for(int i=1;i<=len;i++) { for(int j=i+1;j<=len;j++) { result += arr[array[i]][array[j]]; result += arr[array[j]][array[i]]; } } return result; } static void setDiff() { int start[] = new int[N/2+1]; int link[] = new int[N/2+1]; int startIdx = 1; int linkIdx = 1; for(int i=1;i<=N;i++) { if(visit[i]) { start[startIdx++]= i; } else { link[linkIdx++]= i; } } int startScore = getScore(start); int linkScore = getScore(link); int result = Math.abs(startScore - linkScore); if(result < ans) { ans = result; } }
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.
예를 들면,
| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |
로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.
마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.
풀이
이전에 밟은 땅의 점수를 의미하는 tmp 변수를 이용한다.
문제에서 이전에 밟은 땅은 연속적으로 밟을 수 없다고 하였으므로 이 부분 주의하여 이전에 밟지 않은 땅만 계산한다.
이전에 밟은 땅 점수 + 현재 밟은 땅의 점수를 계산하여 가능한 모든 경우의 수에 최대값을 계산하면 되는 문제