글 읽기 - (KOI 어린이집 줄세우기)머리를 굴려봐도 어쩔 수 없네..

hswoo8 8년 전 1

알고리즘 적으로

총개수 - 연속된 숫자 개수 = 옮기는 수 라고 생각하고 풀고있는데 안풀리네요

제게 가르침을 선사좀..

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstdlib>

using namespace std;

vector <int> v;

int count1 = 1;

int t;

void search(int k){

for (int r=k+1; r < t; r++){

if (v[k] < v[r]){

++count1;

k = r;

}

}

}

int main(){

cin >> t;

int n;

for (int i = 0; i < t; i++){

cin >> n;

v.push_back(n);

}

vector <int> s;

for (int i = 0; i < v.size(); i++){

for (int j = i ; j < v.size(); j++){

if (v[i] < v[j]){

++count1;

search(j);

}

s.push_back(count1);

count1 = 1;

}

count1 = 1;

}

sort(s.begin(), s.end());

cout << t-s[s.size()-1];

return 0;

}

kyma123 8년 전 9

연속된 수가 아니라 LIS의 길이를 찾는 문제일거에요.

증가하는 순으로 배치돼있는 가장 긴 아이들의 조합을 기준으로 잡으면 걔네는 건드릴 필요 없이 나머지만 옮김으로써 줄 세울 수 있겠죠.

hswoo8 8년 전 0

말을 잘못했네요 증가하는 순으로 배치되어있는 가장 긴 수를 구했고 20자리 수까지 경우에수 다때려박았는데도 잘 나오는데 어디가 잘못된건지..ㅜㅜ

kyma123 8년 전 0

LIS를 구하는 코드가 잘못된 것 같네요.

7

1 2 6 7 3 4 5

의 경우 1, 2, 6, 7을 LIS로 생각하고 구하고 있네요.

LIS를 구하는 알고리즘은 보통 동적계획법을 이용합니다.

hswoo8 8년 전 0

정말 감사합니다

shinywb 7년 전 0

우와~ 진짜 다들 대단하시네요

cokcjswo 7년 전 0

kyma123님 감명받고 갑니다... 직관이 좋으시네요 !!

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