글 읽기 - 알고리즘의 틀린점을 모르겠어요

jukdang 3년 전 0

이문제를 풀때 알고리즘을

1. 전기줄 별로 cross되있는 수를 찾는다.

2. cross되있는 수가 가장큰 전깃줄을 지운다.

반복 → cross가 모두 0일때 탈출

지운 전깃줄의 수 출력

이렇게 짜보았는데 어떨때 틀린가요?

(정렬후 LIS하는 것과 많이 다른가요?)

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

int main(){
	int n;
	scanf("%d",&n);
	int power[n][2];
	int cross[n];
	int erase[n];
	for(int i=0;i<n;i++){
		scanf("%d %d",&power[i][0],&power[i][1]);
		erase[i]=0;
	}
	int end=1;
	while(end!=0){
		end=0;
		for(int i=0;i<n;i++){
			cross[i]=0;
		}
		for(int i=0;i<n;i++){
			if(erase[i]==0){	
				for(int j=0;j<n;j++){
					if(i!=j&&erase[j]==0){
						if(power[i][0]>power[j][0]&&power[i][1]<power[j][1]){
							cross[i]++;
						}
						else if(power[i][0]<power[j][0]&&power[i][1]>power[j][1]){
							cross[i]++;
						}
					}
				}
			}
		}
		int large=0,large_index;
		for(int i=0;i<n;i++){
			end+=cross[i];
			if(large<cross[i]){
				large=cross[i];
				large_index=i;
			}
		}
		if(large>0){
			erase[large_index]=1;
		}
	}
	int res=0;
	for(int i=0;i<n;i++){
		if(erase[i]==1) res++;
	}
	printf("%d",res);
}

taejune9721 3년 전 1

그런데, 이 방식이 동적계획법이라고 생각하세요?

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

문제

문제

출처

ICPC

알고리즘의 틀린점을 모르겠어요

jukdang 3년 전 0

taejune9721 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말