글 읽기 - 제가 푼 방식 맞는지 봐주세요ㅠㅠㅠㅠ

sirorong2 5년 전 0

예제는 맞는데 채점하면 틀리다고 나오네요

우선 돌맹이가 가장 많은 라인을 가로와 세로에서 고르고

하나씩 지워가면서 전체 돌 수에서 감소시킴

k==0일경우 빠져나가서 결과를 도출했는데 어디서 틀린건지 알 수 있을까요!!???

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

public class Main {
	public static void main(String [] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer sToken = new StringTokenizer(br.readLine(), " ");
		int n = 0,k = 0;
		while(sToken.hasMoreTokens()) {
			n = Integer.parseInt(sToken.nextToken());
			k = Integer.parseInt(sToken.nextToken());
		}
		int [][] map = new int[n+1][n+1];
		for(int i=0;i<k;++i) {
			StringTokenizer token = new StringTokenizer(br.readLine(), " ");
			int a=0,b=0;
			while(token.hasMoreTokens()) {
				a = Integer.parseInt(token.nextToken());
				b = Integer.parseInt(token.nextToken());
			}
			map[a][b] = 1;
		}
		
		int resCount = 0;
		while(true) {
			resCount++;
			//System.out.println("res = "+resCount);
			int row =0;
			int rowidx = 0;
			int rowmax = 0;
			int col =0;
			int colidx = 0;
			int colmax = 0;
			for(int i=1;i<=n;++i) {
				int rowtemp = 0;
				int coltemp = 0;
				for(int j=1;j<=n;++j) {
					if(map[i][j] == 1) {
						rowtemp++;
					}
				}
				for(int j=1;j<=n;++j) {
					if(map[j][i]==1) {
						coltemp++;
					}
				}
				if(rowmax<rowtemp) {
					rowmax= rowtemp;
					rowidx = i;
				}
				if(colmax<coltemp) {
					colmax = coltemp;
					colidx = i;
				}
			}
			//돌맹이 가장 많은 라인 찾기
			if(colmax<rowmax) {
				for(int i=1;i<=n;++i) {
					if(map[rowidx][i]==1) {
						map[rowidx][i] = 0;
						k--;
					}
				}
			}else {
				for(int i=1;i<=n;++i) {
					if(map[i][colidx] == 1) {
						map[i]
								[colidx] = 0;
						k--;
					}
				}
			}
			//돌맹이가 가장 많은라인 찾아서 돌맹이 줍기
			//총 돌맹이 개수도 줄여주기
			
			if(k==0) {
				break;
			}
			//돌맹이가 다 없어지면 브레이크!
		}
		System.out.println(resCount);
		
	}
}

lim551 5년 전 1

XXOO

XOXO

XOOX

X가 돌멩이일 때 반례입니다.

힌트는 단순한 구현으로 풀리는 문제가 아닙니다.

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

문제

문제

출처

ICPC

제가 푼 방식 맞는지 봐주세요ㅠㅠㅠㅠ

sirorong2 5년 전 0

lim551 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말