[Java] 16439번 : 치킨치킨치킨

https://www.acmicpc.net/problem/16439

16439번: 치킨치킨치킨

 

치킨이 먹고싶어서 그냥 이 문제를 풀었는데,,,목이 턱턱 맥혔다,,,,

 

정말 내 기분이잖아요~!~!~!~!

 

실버4라고 만만하게 봤는데,,,난 어려웠다,,,

조합으로 좀 복잡하게 풀었다! 

 

간단하게 로직을 설명하자면, 무조건 3가지 종류 밖에 안되기 때문에 열을 기준으로 조합을 돌려서, 그 결과값을 문자열(str)로 저장하고, 다시 숫자로 변경해서 새로운 out 배열에 저장했다.

if(depth==3) {
    String str="";
    int sum=0;
    for(int i=0;i<tmp.length;i++) {
        if (visited[i]) {
            str += (tmp[i] + " ");
        }
    }
    String cTmp[] = str.split(" ");
    for(int i=0;i<n;i++) {
        for(int j=0;j<3;j++) {
            out[i][j] = a[i][Integer.parseInt(cTmp[j])-1];
        }
    }
    for(int i=0;i<n;i++) {
        int max=Integer.MIN_VALUE;
        for(int j=0;j<3;j++) {
            max = Math.max(max, out[i][j]);
        }
        sum+=max;
    }
    ret = Math.max(ret, sum);
    return;
}

 

out 배열은 무조건 n * 3 행렬이기 때문에 초기에 지정해두었고, tmp 라는 임시 배열을 만들어서 1부터 m까지 저장을 해서 이 부분을 조합을 돌렸다! 

public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;

    st = new StringTokenizer(br.readLine());

    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());

    a = new int[n][m];
    visited = new boolean[m];
    tmp = new int[m];
    out = new int [n][3];

    for(int i=0;i<n;i++) {
        st = new StringTokenizer(br.readLine());
        for(int j=0;j<m;j++) {
            a[i][j] = Integer.parseInt(st.nextToken());
        }
    }

    for(int i=0;i<m;i++) {
        tmp[i]=i+1;
    }

    combi(tmp, 0,0);

    System.out.print(ret);

}

 

처음에는 런타임 에러가 났었다! 예제가 한자리수라서 한자리수만 고민해서 생겼던 오류였다! 

문자열 자르는거 까먹어서 블로그 참고 ㅎ

https://jamesdreaming.tistory.com/84

[ 자바 코딩 ] Java split() 함수로 문자열 자르기

이렇게 되어있는 부분을 사실은 ,,,

Integer.parseInt(cTmp[j])-1

 

이렇게 한자리수만 고려해서 인덱스 초과 문제가 생겼다. ! 

str.charAt(j)-'0'-1

 

[전체코드]

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

public class Main {

    static int n, m, ret;
    static int a[][];
    static int out[][];
    static boolean visited[];
    static int tmp[];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        a = new int[n][m];
        visited = new boolean[m];
        tmp = new int[m];
        out = new int [n][3];

        for(int i=0;i<n;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0;i<m;i++) {
            tmp[i]=i+1;
        }

        combi(tmp, 0,0);

        System.out.print(ret);

    }

    public static void combi(int tmp[], int start, int depth) {
        if(depth==3) {
            String str="";
            int sum=0;
            for(int i=0;i<tmp.length;i++) {
                if (visited[i]) {
                    str += (tmp[i] + " ");
                }
            }
            String cTmp[] = str.split(" ");
            for(int i=0;i<n;i++) {
                for(int j=0;j<3;j++) {
                    out[i][j] = a[i][Integer.parseInt(cTmp[j])-1];
                }
            }
            for(int i=0;i<n;i++) {
                int max=Integer.MIN_VALUE;
                for(int j=0;j<3;j++) {
                    max = Math.max(max, out[i][j]);
                }
                sum+=max;
            }
            ret = Math.max(ret, sum);
            return;
        }

        for(int i=start;i<tmp.length;i++) {
            if(!visited[i]) {
                visited[i] = true;
                combi(tmp, i+1, depth+1);
                visited[i] = false;
            }
        }
    }

}

 

그래도 풀었당~!~!!