글 읽기 - 반례 부탁드립니다..

lhy332 3년 전 1

여러가지 반례를 테스트 해봤는데 답이 제대로 나오는거 같은데...채점 진행하다가 중간에서 틀렸습니다라고 나오네요..

반례 부탁드립니다.

[테스트 케이스]

1 3 2
2 1 4
답: 6

2 3 3
1 1 1
1 1 1
답: 3

2 3 1
1 1 1
1 1 1
답: 1

2 3 1
1 1 1
1 6 1
답: 6

2 3 3
6 1 6
1 6 1
답: 18

2 3 3
10000 10000 10000
1 6 1
답: 20006

2 3 3
10000 10000 10000
10000 10000 10000
답: 30000

3 3 1
10000 10000 1
10000 2 1
10000 10000 10000
답: 10000

3 3 2
100 1000 1
1000 2 1
10000 10 10000
답: 20000

3 3 4
100 10 1
1000 2 1
10000 10 10000

답: 20102

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

public class Main {

    static int row;
    static int col;
    static int numOfChoice;
    static int[] choice;
    static int[][] inputMap;
    static boolean[][] occupied;
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = {  0, 1, 0,-1 };
    static int max = Integer.MIN_VALUE;

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

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

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

        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
        numOfChoice = Integer.parseInt(st.nextToken());

        choice = new int[numOfChoice];
        inputMap = new int[row][col];
        occupied = new boolean[row][col];

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

        getMax(0);
        System.out.println(max);

    }

    public static void getMax(int index) {

        if (index == numOfChoice) {
            int sum = 0;
            for (int i = 0 ; i < numOfChoice; i++) {
                sum += choice[i];
            }

            if (sum > max){
                max = sum;
            }

            return;
        }

        int max = Integer.MIN_VALUE;
        int maxX = 0;
        int maxY = 0;

        for (int i = 0 ; i < row ; i++){
            for (int j = 0 ; j < col ; j++){
//                System.out.println("check i , j : " + i + " " + j + " " + check(i,j));
                if(check(i,j)){
                    if (inputMap[i][j] > max){
                        max = inputMap[i][j];
                        maxX = i;
                        maxY = j;
                    }
                }
            }
        }

        occupied[maxX][maxY] = true;

//        for(int i = 0 ; i < row; i++){
//            for (int j = 0 ; j < col; j++){
//                System.out.print(occupied[i][j] + " ");
//            }
//            System.out.println();
//        }


        choice[index] = inputMap[maxX][maxY];
        getMax(index + 1);

    }


    public static boolean check( int x, int y){

        if (occupied[x][y]) {
                return false;
            }


        if (x -1 >= 0){
            if (occupied[x-1][y]) {
                return false;
            }
        }

        if (y+1 < col){
            if (occupied[x][y+1]){
                return false;
            }
        }

        if (x+1 < row){
            if(occupied[x+1][y]){
                return false;
            }
        }
        if (y-1 >= 0){
            if(occupied[x][y - 1]){
                return false;
            }
        }
        return true;
    }
}

nahwasa 3년 전 6

반례입니다.

2 2 2
-1 -2
-3 -5

예상출력 : -5
출력 : -6

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 부탁드립니다..

lhy332 3년 전 1

nahwasa 3년 전 6

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말