글 읽기 - 문제를 이해 못한 것 같아요. 못 풀겠네요

sert 7년 전 0

제가 기존 알고리즘을 잘 몰라서 제 생각난대로 막 만들었는데

DFS, BFS나 DP같은 것을 잘 모릅니다.

근데 보통 이걸 모르고 짜면 시간초과가 뜨던데

지금은 문제 파악도 제대로 못했는지 '틀렸습니다'가 뜨네요.

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[][] matrix = new int[n][n];
		String tmp = null;
		int cnt = 0;
		while (cnt < n) {
			tmp = br.readLine();
			for (int i = 0; i < n; i++) {
				matrix[cnt][i] = Character.getNumericValue(tmp.charAt(i));
			}
			cnt++;
		}
		int result = 1;
		int owner = 0;
		int price = 0;
		int[] visit = new int[n];
		Boolean run = true;
		while (run) {
			int tmp1= owner;			
			for (int i = 0; i < n; i++) {
				if (visit[owner] == 0 && price <= matrix[owner][i]) {
					owner = i;
					price = matrix[owner][i];
					visit[owner] = 1;
					break;
				}
			}
			if(tmp1 == owner){
				run = false;
			}
		}
		for(int i=0; i<n; i++){
			if(visit[i] ==1){
				result +=1;
			}
		}
		System.out.println(result);
	}
}

koosaga 7년 전 1

해법은!

배우는 겁니다.

(추천서 : 구종만 - 프로그래밍 대회를 위한 알고리즘 문제해결 전략)

(저 문제는 bitmask dp라는 걸 알아야 수월하게 푸실 수 있을 거에요.)

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

문제

문제

출처

ICPC

문제를 이해 못한 것 같아요. 못 풀겠네요

sert 7년 전 0

koosaga 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말