백준 14889번
https://www.acmicpc.net/problem/14889

문제

---

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

생각하기

---

문제가 그렇게 어렵다고 생각을 하지는 않았는데, 팀을 나눠서 재귀를 구현하는 부분을 도저히 생각할 수 없어서 다른 분들의 코드를 참고해서 문제를 해결했다.

그래서 이번에는 풀이는 다른 분들의 코드를 링크로 남기고 이 문제를 해결하면서 신선한 충격을 받게 되서 그 부분을 중점적으로 다뤄보려고 한다.

풀이 : 백준 14889 풀이 링크

동작

코틀린을 접한지 얼마안되서 그런지 다른 분들이 작성하신 코드를 보면 정말 눈이 휘둥그레지는 경우가 많다
이렇게도 작성할 수 있다는 걸 깨닫는 경우가 너무 많아서 이다.

지금까지 문제를 내가 풀던 방식은 아무래도 자바에서 코틀린으로 넘어오다 보니 자바에서 코딩하던 방식을 그대로 유지해서 코딩을 했었는데, 코틀린은 자바가 모체이긴 하지만 그래도 코틀린에서만 쓸 수 있는 코드 방식이 많다보니 그걸 익히는데 많은 시간이 필요했고, 다른 분들의 자료를 많이 참고해야했다

오늘은 fun main() 문 안에서 다른 함수를 만들어서 작동 시키는 것을 알게 되었다.

자바에서 익명함수와 비슷한 것 같은데 맞는지는 잘 모르겠다.

자바에서는 Main class가 있고 그 안에서 함수를 만들다보니 static 개념이 있었는데, 코틀린에서는 static이 붙지를 않다보니 혼동이 오는것 같다.

암튼 fun main() 안에서 함수를 만들어서 실행을 할 수 있다는 것을 알게되었다.

첫 번째 방법을 통해서 실행을 하니 확실히 static 공간을 활용하는 곳이 적다보니 메모리도 효율성이 좋았고,
함수도 main 내부에서 실행이 되니까 속도적인 효율성도 더 좋았던 것 같다.

하지만, 장단점의 유무가 있을테니 첫 번째 방법을 터득하더라도 두 번째 방법도 같으 쓸 수 있는 방향으로 공부를 해야겠다는 생각을 했다.

코드

---

Kotlin

방법 1

import java.io.*;
import java.util.*;

fun main() {
    var br = BufferedReader( InputStreamReader(System.`in`) )
    var N = br.readLine().toInt();
    var arr = Array(N){Array(N) {0}} // Int형 2차원 배열 생성 및 초기화
    var visit = Array<Boolean>(N, {false});
    var result = Integer.MAX_VALUE;

    for(i in 0..N-1) {
        var st = StringTokenizer(br.readLine());
        for(j in 0..N-1) {
            arr[i][j] = st.nextToken().toInt()
        }
    }

    fun diff() {
        var team_start = 0;
        var team_link = 0;

        for(i in 0..N-2) {
            for(j in i+1..N-1) {

                if(visit[i] && visit[j]) {
                    team_start += arr[i][j] + arr[j][i];
                }
                else if( !visit[i] && !visit[j] ) {
                    team_link += arr[i][j] + arr[j][i];
                }
            }
        }

        var dif = Math.abs(team_start - team_link);
        result = Math.min(result, dif);

        if(result == 0) {
            println(result)
            System.exit(0);
        }

    } // End of diff

    fun DFS(idx : Int, depth : Int) {

        if(depth == N/2) {
            diff();
            return;
        }

        for(i in idx..N-1) {
            if(visit[i]) continue;

            visit[i] = true;
            DFS(i+1, depth + 1);
            visit[i] = false;
        }

    }// End of DFS

    DFS(0, 0)
    println(result)

} // End of main

방법 2

import java.io.*;
import java.util.*;

private lateinit var arr : Array<Array<Int>>
private lateinit var visit : Array<Boolean>
private var N = 0;
private var result = Integer.MAX_VALUE;

fun main() {
    var br = BufferedReader( InputStreamReader(System.`in`) )

    N = br.readLine().toInt();
    arr = Array(N){Array(N) {0}} // Int형 2차원 배열 생성 및 초기화
    visit = Array<Boolean>(N, {false});

    for(i in 0..N-1) {
        var st = StringTokenizer(br.readLine());
        for(j in 0..N-1) {
            arr[i][j] = st.nextToken().toInt()
        }
    }

    DFS(0, 0)
    println(result)

} // End of main

fun DFS(idx : Int, depth : Int) {

    if(depth == N/2) {
        diff();
        return;
    }

    for(i in idx..N-1) {
        if(visit[i]) continue;

        visit[i] = true;
        DFS(i+1, depth + 1);
        visit[i] = false;
    }

}// End of DFS

fun diff() {
    var team_start = 0;
    var team_link = 0;

    for(i in 0..N-2) {
        for(j in i+1..N-1) {

            if(visit[i] && visit[j]) {
                team_start += arr[i][j] + arr[j][i];
            }
            else if( !visit[i] && !visit[j] ) {
                team_link += arr[i][j] + arr[j][i];
            }
        }
    }

    var dif = Math.abs(team_start - team_link);
    result = Math.min(result, dif);

    if(result == 0) {
        println(result)
        System.exit(0);
    }

} // End of diff