14620 꽃길

시도1

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;

public class Main{
    static class Point{
        int x;
        int y;
        Point(int x, int y){
            this.x=x;
            this.y=y;
        }
    }
    static int min = Integer.MAX_VALUE;
    static Point p;
    static int arr[][];
    static int n;
    static boolean isVisited[][];
    public static void solve(int i, int j){
        //들어온인자의 상하좌우에 대해서
        if(i+1 < n && j+1 < n && i-1 >=0 && j-1 >= 0){
            //꽃을 심을 수 있는곳이면 상,하,좌,우 탐색을 한다
            if(!isVisited[i][j] && !isVisited[i+1][j] && !isVisited[i][j+1] &&
                    !isVisited[i][j-1] && !isVisited[i-1][j]){
                //꽃을 심는다
                int temp = arr[i][j] + arr[i][j+1] + arr[i+1][j] + arr[i-1][j] + arr[i][j-1];
                if(min >= temp){
                    min = temp;
                    p = new Point(i,j);
                }
            }

        }
    }
    public static void visit(){
        int r = p.x;
        int c = p.y;
        //방문했던곳의 상하좌우만 방문처리
        isVisited[r][c] = true;
        isVisited[r+1][c] = true;
        isVisited[r][c+1] = true;
        isVisited[r][c-1] = true;
        isVisited[r-1][c] = true;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        isVisited = new boolean[n][n];
        for(int i=0;i<n;i++){
            String input[] = br.readLine().split(" ");
            for(int j=0;j<n;j++){
                arr[i][j] = Integer.parseInt(input[j]);
            }
        }
        int result=0;
        //꽃을 세번심는다
        for(int k=0;k<3;k++){
            min = Integer.MAX_VALUE;
            //모든 지점에 대해서 꽃을 심을 수 있는곳인지 판별한다
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    solve(i,j);
                }
            }
            result+=min;
            //point에 대한 방문처리 (꽃을심는다)
            visit();
        }

        bw.write(result+"");
        bw.flush();
        bw.close();
    }
}

가장최소값만을 찾는데.. 가장최솟값만을 찾는게 합이 최소인것을 보장해주지않을때도있을것같다
왜냐하면 가장최솟값을 visited처리해줌으로써 그다음 최솟값을 처리못할수도있기때문에 합이 최소인것을 찾기위해선 저코드말고 다르게 짜야할것같다.

15661

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;

public class Main{
    static int arr[][];
    static int min = Integer.MAX_VALUE;
    static boolean isTeamA[];
    public static void solve(int depth, int idx){
        if(depth>=arr.length){
            //능력치 차이의 최소를 구한다
            int teamA=0;
            int teamB=0;
            boolean allTeamA = true;
            boolean allTeamB = true;
            for(int i=0;i<isTeamA.length;i++){
                for(int j=i+1;j<isTeamA.length;j++){
                    if(!isTeamA[i] || !isTeamA[j]) allTeamA = false;
                    if(isTeamA[i] || isTeamA[j]) allTeamB = false;
                    if(isTeamA[i] && isTeamA[j]){
                        teamA+=(arr[i][j]+arr[j][i]);
                    }
                    if(!isTeamA[i] && !isTeamA[j]){
                        teamB += (arr[i][j] + arr[i][j]);
                    }
                }
            }
            int temp = Math.abs(teamA-teamB);
            if(allTeamA || allTeamB) temp = Integer.MAX_VALUE;
            min = Math.min(min, temp);
            return;
        }
        for(int i=idx;i<arr.length;i++){
            if(!isTeamA[i]){
                isTeamA[i] = true;
                solve(depth+1, i+1);
                isTeamA[i] = false;
            }

        }

    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        isTeamA = new boolean[n];
        for(int i=0;i<n;i++){
            String input[] = br.readLine().split(" ");
            for(int j=0;j<n;j++){
                arr[i][j] = Integer.parseInt(input[j]);
            }
        }
        solve(0,0);
        bw.write(min+"");
        bw.flush();
        bw.close();
    }
}

• 이코드는 if문 내부가 한번만 호출된다

2961

 public static void solve(int depth, int idx){
        if(idx ==n){
            if(!list.isEmpty()){
                int sSum=1;
                int dSum=0;
                for(Integer i: list){
                    sSum *= flavors[i].s;
                    dSum += flavors[i].d;
                }
                min = Math.min(min, Math.abs(sSum-dSum));
            }
            return;
        }
        //뒤에있는것을 무조건 선택하게함
        //중간에있는것만 선택하는것이 안됨
        //오름차순 + 뒤에 더 큰수가있으면 무조건출력 이런 로직임
        for(int i=idx;i<n;i++){
            list.add(i);
            int idx2= list.size()-1;
            solve(depth+1, i+1);
            list.remove(idx2);
        }
    }