저번주는 엄청 바쁜 시간들을 보냈다.
면접 두 개에 주말에 코테도 있었다...
면접을 보면서 느낀것은 현직자의 입장에서 나는 프로젝트 경험이 많은 것이 아니구나
그리고 CS 공부를 정말 겉핧기 식으로 했었구나를 느꼈다.
그리고 그나마 가장 자신있는 부분이 프론트엔드인데, 자바스크립트나 관련 라이브러리를 써본 경험은 있지만 특정 상황에서 동작하기 위해 어떤 함수를 써야하는지에 대한 질문에 답을 못했다.
그래서 이제는 알고리즘 뿐만 아니라 프론트 관련 CS 공부도 같이 병행하며 포스팅을 하려고 한다.

📝문제

DP로 풀 수 있지 않을까...? 싶었지만 점화식이 도저히 떠오르지 않아서 완전탐색으로 풀었다.
Combination과 비슷한 방법으로 백트래킹을 하면서 어떤 팀인지 표시하고
반을 나눴을 때에 팀별로 최종 스탯을 구한다.

📌코드

package BruteForce;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ14889 {
  /**
   * 백트래킹과 브루트포스로 반을 나눈다
   */

  static int[][] stat;
  static boolean[] isStart;
  static int n;
  static int answer = Integer.MAX_VALUE;

  static void solution(int s, int cnt){
    if(cnt == n/2){
      int start = 0;
      int link = 0;
      for(int i = 0; i < n; i++){
        if(isStart[i]){
          for(int j = 0; j < n; j++){
            if(isStart[j]) start += stat[i][j];
          }
        } else {
          for(int j = 0; j < n; j++){
            if(!isStart[j]) link += stat[i][j];
          }
        }
      }
      answer = Math.min(Math.abs(start - link), answer);
      return;
    }
    for(int i = s; i < n; i++){
      isStart[s] = true;
      solution(i+1, cnt+1);
      isStart[s] = false;
    }
  }

  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    stat = new int[n][n];
    StringTokenizer st;
    for(int i = 0; i < n; i++){
      st = new StringTokenizer(br.readLine());
      for(int j = 0; j < n; j++){
        stat[i][j] = Integer.parseInt(st.nextToken());
      }
    }
    isStart = new boolean[n];
    solution(0, 0);
    System.out.println(answer);
  }
}