강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.
스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.
보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)
강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오. 만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력한다.
입력
첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.
출력
첫째 줄에 강호가 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다. 만약, 엘리베이터로 이동할 수 없을 때는 "use the stairs"를 출력한다.
접근방법 및 풀이
- BFS를 이용하여 버튼를 누르는 최소횟수를 탐색한다.
- 탐색 중 도착한 층은 방문체크한다.
- 버튼을 누르는 경우 유효층으로 이동(방문이 안되었고 1층이상 F층 이하)가능하면 이동한다.
- 목표층에 도달할때 까지 진행한 후 찾지 못했다면 use the stairs를 출력한다.
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#define VMAX 1000001
using namespace std;
int height;
int src, dst;
int u,d;
int v[VMAX]={0};
int result=-1;
void bfs(){
queue<pair<int,int>> q;
q.push({src, 0});
v[src]=1;
while(!q.empty()){
int x = q.front().first;
int c = q.front().second;
q.pop();
if(x==dst){
result = max(result, c);
}
if(x+u <= height && v[x+u]==0){
v[x+u]=1;
q.push({x+u, c+1});
}
if(x-d >= 1 && v[x-d]==0){
v[x-d]=1;
q.push({x-d, c+1});
}
}
}
int main()
{
cin >> height >> src >> dst >> u >> d;
if(src == dst){
printf("0");
return 0;
}
bfs();
if(result==-1){
cout << "use the stairs";
}else{
cout << result;
}
return 0;
}
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.
어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.
6
8
2
6
2
3
2
3
4
6
6
7
3
3
2
7
2
5
3
6
8
9
5
2
7
이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.
6
8
2
6
2
3
2
3
4
6
6
7
3
3
2
7
2
5
3
6
8
9
5
2
7
물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다).
또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.
6
8
2
6
2
3
2
3
4
6
6
7
3
3
2
7
2
5
3
6
8
9
5
2
7
이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.
어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.
입력
첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.
출력
첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.
접근방법 및 풀이
- 안전영역의 수를 개산하기 위해 BFS를 사용하였다.
- 물의 높이가 최소1부터 최대 100까지 이므로 100가지의 경우의 물의 상태에 대해 모두 고려해준다.
- 각각의 경우에 대해 지역들이 물에 잠기는지 여부를 초기화해준 후 BFS를 진행한다.
#include <iostream>
#include <algorithm>
#include <queue>
#define VMAX 101
using namespace std;
int n;
int b[VMAX][VMAX];
int v[VMAX][VMAX];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
void bfs(int sx, int sy){
queue<pair<int, int>> q;
q.push({sx,sy});
v[sx][sy] = 1;
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i=0; i<4; i++){
int X = x + dx[i];
int Y = y + dy[i];
if(X>=0 && Y>=0 && X<n && Y<n){
if(v[X][Y]==0){
v[X][Y]=1;
q.push({X,Y});
}
}
}
}
}
int main()
{
cin >> n;
int result=0;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
scanf("%d", &b[i][j]);
}
}
for(int k=0; k<=100; k++){ // 물높이 0 부터 100까지 각각의 경우의 집합수를 구한다.
int temp=0;
for(int i=0; i<n; i++){ // 물높이에 따른 v배열 즉 물의 잠기는 지역을 표시한다..
for(int j=0; j<n; j++){
v[i][j]=0;
}
}
for(int i=0; i<n; i++){ // 물높이에 따른 v배열 즉 물의 잠기는 지역을 표시한다..
for(int j=0; j<n; j++){
if(b[i][j] <= k){
v[i][j] = 1;
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(v[i][j] == 0){
bfs(i,j);
temp++;
}
}
}
result = max(result, temp);
}
cout << result;
return 0;
}
우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.
여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.
입력
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.
각 사람의 부모는 최대 한 명만 주어진다.
출력
입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.
문제접근 및 풀이
- DFS 혹은 BFS를 사용하여 간단히 풀수 있다.
- 촌수를 계산해야 하는 두 사람을 각각 시작과 끝 노드로 두어 탐색을 진행한다.
#include <iostream>
#include <vector>
#include <queue>
#define VMAX 101
using namespace std;
vector<int> a[VMAX];
int v[VMAX]={0};
int bfs(int src, int dst){
queue<pair<int, int>> q;
q.push({src, 0});
v[src]=1;
while(!q.empty()){
int x = q.front().first;
int c = q.front().second;
q.pop();
if(x==dst){
return c;
}
for(int i=0; i<a[x].size(); i++){
int y = a[x][i];
//printf("x:%d y:%d\n",x,y);
if(v[y]==0){
v[y]=1;
q.push({y,c+1});
}
}
}
return -1;
}
int main(){
int n; cin >> n;
int src, dst; cin >> src >> dst;
int m; cin >> m;
for(int x,y,i=0; i<m; i++){
scanf("%d %d", &x, &y);
a[x].push_back(y);
a[y].push_back(x);
}
int result = bfs(src, dst);
printf("%d", result);
}
*/
그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리는 분 단위의 시간을 나타낸다. 두 지점 a와 b를 연결하는 도로는 도로(a,b)로 표시한다.
그림 1
예를 들어 도로(1,2)와 도로(2,3)를 통하여 지점1에서 지점3으로 갈 때 걸리는 시간은 3분이다. 도로는 모두 양방향이라고 가정하므로 도로(a,b)와 도로(b,a)를 지날 때 걸리는 시간은 항상 같다고 한다.
어떤 범죄용의자가 입력 데이터에 표시된 도시로 진입하여 이 도시를 가장 빠른 시간 내에 빠져나가고자 한다. 그런데 이 사실을 알고 있는 경찰이 어떤 하나의 도로(에지)를 선택하여 이 도로에서 검문을 하려고 한다. 따라서 용의자는 이 도로를 피해서 가장 빠르게 도시를 탈출하고자 한다. 이 경우 경찰이 검문을 위하여 선택하는 도로에 따라서 용의자의 가장 빠른 탈출시간은 검문이 없을 때에 비하여 더 늘어날 수 있다.
문제는 도로검문을 통하여 얻을 수 있는 탈출의 최대 지연시간을 계산하는 것이다. 추가설명은 다음과 같다.
두 개의 지점을 직접 연결하는 도로가 있는 경우, 그 도로는 유일하다.
도시의 지점(노드)은 1에서 N번까지 N개의 연속된 정수로 표시된다.
용의자가 도시에 진입하는 지점은 항상 1번이고 도시를 빠져 나가기 위하여 최종적으로 도달해야하는 지점은 항상 N번 지점이다.
용의자는 검문을 피해서 가장 빨리 도시를 빠져나가고자 하고, 경찰은 적절한 도로를 선택하여 이 용이자들의 탈출시간을 최대한 지연시키고자 한다.
각 도시 지점 간을 이동하는 시간은 항상 양의 정수이다.
입력 도시의 도로망에 따라서 경찰이 어떤 도로를 막으면 용의자는 도시를 탈출하지 못할 수도 있다. 이 경우 검문으로 인하여 지연시킬 수 있는 탈출시간은 무한대이다. 이 경우에는 -1을 출력해야 한다.
그림 1에서 볼 때 검문이 없을 경우 용의자가 도시를 탈출하는데 걸리는 시간은 4분이다. 만일 경찰이 도로(4,3)을 막으면 그 탈출시간을 지연시킬 수 없으므로 지연시간은 0이다. 만일 도로(2,3)을 막으면, 용의자들이 가장 빠르게 탈출할 수 있는 시간은 5분이므로 탈출지연시간은 1분이고, 도로(3,6)을 막으면 탈출지연시간은 2분이다.
여러분은 입력 데이터에 표시된 도로망을 읽고, 경찰이 한 도로를 막고 검문함으로써 지연시킬 수 있는 최대시간을 정수로 출력하여야한다. 만일 지연효과가 없으면 0을 출력해야하고, 도시를 빠져나가지 못하게 만들 수 있으면(지연시간이 무한대) -1을 출력해야 한다.
입력
첫 줄에는 지점의 수를 나타내는 정수 N(6 ≤ N ≤ 1000)과 도로의 수 M(6 ≤ M ≤ 5000)이 주어진다. 그 다음 이어 나오는 M개의 각 줄에는 도로(a, b)와 그 통과시간 t가 a b t 로 표시된다. 단 이 경우 a < b 이고 1 ≤ t ≤ 10000이다.
출력
경찰이 하나의 도로를 막음으로써 지연시킬 수 있는 최대 시간을 정수로 출력한다. (단, 그 지연시간이 무한대이면 -1을 출력해야 한다.)
문제접근 및 고려사항, 풀이
- dijkstra algorithm를 응용하여 풀 수 있다.
- 도로는 유일하고 양방향이며, 가중치는 양의정수이다.
- 어떤 도로를 막아 탈출 불가능하게 만들면 -1 - 도로를 막아 탈출시간을 지연할 수 있는 최대값 구하기 - 지연효과가 없으면 0이라는 것이 무엇을 의미하는 지 생각해보니 도로검문 전 부터 아예 탈출 불가능한 경우를 의미하는 것이었다.
1. 1번 도시에서부터 n번 도시로의 dijkstras 진행
-> 만약 탈출불가능 한 경우 0 출력(도로검문 없이도 탈출불가능하면 도로검문으로 인한 지연효과가 없으므로)
-> 도로검문 없는 경우의 용의자의 최단경로 값을 확보한다. 2. 1을 진행하면서 opt에 다가 거치는 도로들을 담는다. 3. opt에 담긴 각 도로에 대해 해당 도로를 막는 경우에 대해 dijkstras를 진행하면서 기존 최대값보다 비교하여 최대값을 갱신한다. -> 만약 탈출불가능 (최대값이 INF)이면 -1 -> INF 아니면 기존 최소값과 차이를 구해서 max와 비교 후 갱신 -> opt는 도로검문 없은 경우의 최단경로로 고려된 도로들의 집합이므로 3에서 구한 최대값이 1에서 구한 최단경로 이동 가중치값과 같을 수 없다.
#include <iostream>
#include <vector>
#include <queue>
#define VMAX 1001
#define INF 987654321
using namespace std;
vector<pair<int,int>> v[VMAX];
vector<pair<int,int>> opt;
int dist[VMAX];
int n;
void dijkstras1(int start){
priority_queue<pair<int,int>> pq;
for(int i=0; i<=n; i++) dist[i] = INF;
dist[1]=0;
pq.push({-0, 1});
while(!pq.empty()){
int x = pq.top().second;
int wx = -pq.top().first;
pq.pop();
if(x==n) return ;
for(int i=0; i<v[x].size(); i++){
int y = v[x][i].first;
int wy = v[x][i].second;
if(dist[y] > dist[x] + wy){
dist[y] = dist[x] + wy;
pq.push({-dist[y], y});
opt.push_back({x,y});
}
}
}
}
void dijkstras2(int start, pair<int,int> a){
int tx = a.first;
int ty = a.second;
priority_queue<pair<int,int>> pq;
for(int i=0; i<=n; i++) dist[i] = INF;
dist[1]=0;
pq.push({-0, 1});
while(!pq.empty()){
int x = pq.top().second;
int wx = -pq.top().first;
pq.pop();
if(x==n) return ;
for(int i=0; i<v[x].size(); i++){
int y = v[x][i].first;
int wy = v[x][i].second;
if(!(y==ty && x==tx) && !(y==tx && x==ty) && dist[y] > dist[x] + wy){
dist[y] = dist[x] + wy;
pq.push({-dist[y], y});
}
}
}
}
int main(){
int m; cin >> n >> m;
int result=0;
for(int x,y,w,i=0; i<m; i++){
scanf("%d %d %d", &x, &y, &w);
v[x].push_back({y,w});
v[y].push_back({x,w});
}
dijkstras1(1);
if(dist[n]==INF){
printf("0");
return 0;
}
int minv = dist[n];
for(int i=0; i<opt.size(); i++){
dijkstras2(1, opt[i]);
if(dist[n]==INF){
printf("-1");
return 0;
}else{
result = max(result, dist[n] - minv);
}
}
printf("%d", result);
}
느낀점
첫 접근때, 최단경로에 해당하는 도로만을 모아서 하나씩 검문하는 것이 불가능하다고 생각했다. 그래서 모든 도로에 대해 각 도로를 검문하도록 했더니 시간초과가 나왔다. 어떻게 최적화 시킬 수 있을까 하고 고민하다가 1->n으로의 최단경로를 이루는 도로들만을 구하는 것은 어렵겠지만 최단경로를 탐색하는 과정에서 거친 도로들을 모으면 이전보다 최적화될것이라고 생각하고 코드를 짰더니 통과가 되었다. 나름의 고민끝에 이전보다 더 코드를 짜 너무 뿌듯했다.
-> 지금 생각해보니,, routing algorithm처럼 각 노드에서 연결된 노드들을 저장시켜서 꼬리물기 방식으로 탐색하면 1->n으로 향하는 최단 경로를 구할 수 있다!
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.
포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.
예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.
입력
첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.
출력
첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.
문제접근 및 풀이
점화식을 통해 해결한다.
i번째 포도주까지 고려한 경우를 생각해보면
3잔연속으로 마실 수 없으므로 다음 시나리오가 존재한다.
1. i-3번째를 마시고 i-1,i번째를 마신다.
2. i-2번째를 마시고 i번째를 마신다.
3. i-1번째를 마시고 i번째를 마시지 않는다. -> 이게 중요했다. i번째를 마시지않고 i-1를 마시는 경우가 더 큰값을 가질수 있다. -> 여러 잔을 건너뛸수 있기 때문이다.
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n; cin >> n;
int a[10001]={0};
int dp[10001]={0};
for(int i=1; i<=n; i++) scanf("%d", &a[i]);
dp[0] = 0;
dp[1] = a[1];
dp[2] = a[1] + a[2];
for(int i=3; i<=n; i++){
dp[i] = max({dp[i-3]+a[i-1]+a[i], dp[i-2]+a[i], dp[i-1]});
}
printf("%d\n", dp[n]);
}
느낀점
점화식의 위력을 알게 되었다. 항상 재귀로 가지치기하는 식으로 dp문제를 해결했었다. 이 문제도 최적을 해를 점화식을 통해 찾기 보다 처음에, 해당 포도주를 먹는 경우 먹지 않는 경우를 재귀형식으로 하여 모든 가능한 경우중 최대값을 찾으려 하니 자연스레 시간초과가 났다. 하지만 점화식을 찾고 O(n)만에 답을 구할 수 있다는 것에 놀랐다. 더 dp 공부를 해야 겠다.
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
접근방식 및 풀이
백트래킹을 통해 모든경우를 탐색하고 가지치기하며 해를 구해나간다.
1. 1번째 행부터 각 행에 대해 각각 1~n까지의 칸에 퀸이 있는 모든 경우를 탐색한다.
2. 탐색 중 해당칸에 퀸을 놓는 것이 허용되면 놓고 그렇지 않으면 리턴한다. -> 가지치기
3. pos가 n+1까지 다다르면 n개의 퀸을 다 규칙에 맞게 놓게된것을 의미하므로 이때 카운트를 한다.
#include <iostream>
using namespace std;
int n, count=0;
int b[15]={0}; // max_N : 14
bool check(int pos){
for (int i = 1; i < pos; i++) {
if (b[pos] == b[i] || pos - i == abs(b[pos] - b[i])) {
return false;
}
}
return true;
}
void bt(int pos){
if(pos==n+1){
count++;
return ;
}
for(int i=1; i<=n; i++){
b[pos]=i;
if(check(pos)==true){
bt(pos+1);
}
}
return ;
}
int main(){
cin >> n;
bt(1);
printf("%d", count);
return 0;
}
느낀점
처음에 2차원 배열로 접근했다. n이 13일때 너무 복잡도가 커지길래 해결방법을 계속 생각해보았다. 더 효율적인 가지치기 방법이 있나에만 집중하다가 결국 해답을 보았고 1차원 배열로도 풀이가 가능하다는 것을 알게 되었다. n-queen풀이의 판이 2차원인 것을 곧이곧대로 받아들인 탓에 유연한 사고를 못한게 아쉬웠다.
오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 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
5
6
7
1
2
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이 되고 이 값이 최소이다.
입력
첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.
출력
첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.
문제접근 및 풀이
형성가능한 모든 팀 쌍에 대해 점수를 계산하여 각 팀의 점수차가 최소가 되는 값을 구해야 겠다고 생각했다.
