2개의 댓글이 있습니다.
-
-
astein -
위의 경우를 체크할 필요가 없는 이유는, (인덱스의 편의상 n+1명이 있다고 가정했습니다.)
1명, 2명, 1명일 때는 => [Tn + T0] + [T1 + T0 + Tn-1 + T1] + [Tn-3 + T0] = 3T0 + 2T1 + Tn-3 + Tn-1 + Tn 만큼의 시간이 듭니다.
2명, 1명, 1명으로 하면 => [T1 + T0 + Tn + T1] + [Tn-2 + T0] + [Tn-3 + T0] = 3T0 + 2T1 + Tn-3 + Tn-2 + Tn 만큼의 시간이 들지요
즉, 항상 Tn-1 > Tn-2가 되기 때문입니다 :-)
이 문제는 귀납법으로 증명이 가능합니다. n <= 3일때는 모든 경우를 다 해보고, n > 3일때는 큰 두 명을 처리하고 n-2일때의 반복으로...
16년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
nocut98
문제는 유명한 다리 건너는 데 최소값을 구하는 문제입니다. times; times_) {
한번에 2명이 건너고 1명이 돌아옵니다. 돌아올 때는 건너가 있는 사람 중에 아무나 와도 되구요
사실 눈을 부릅뜨고 보면 2가지 종류밖에 없습니다.
(예를 들어 건너는 데 걸리는 시간이 각각 1, 2, 3, 50, 99, 100이라고 하면요.)
1) 한번에 2명을 건네주는 방법
1,2->
<-1
99, 100->
<-2
2) 한번에 1명을 건네주는 방법
1,100->
<-1
4명 미만인 경우는 각각 처리하면 되구요.
코드도 아래 처럼 간단하게 나옵니다(recursive하게) 처리시간은 무려 O(2^n)이 됩니다.
[code c++]
vector
int doit(int n) {
if(n==3) { return times[n-1] + times[0] + times[1];}
if(n==2) { return times[1];}
if(n==1) { return times[0]; }
if(n>3) {
int a = times[1]+times[0]+times[n-1]+times[1]+doit(n-2);
int b = times[n-1]+times[0]+doit(n-1);
// else cout << "norm" << endl;
return min(a,b);
}
int minTime(vector
times = times_;
int n = sz(times);
sort(all(times));
return doit(n);
}
[/code]
근데, red인 분들의 소스를 보면, 그냥 2명 한꺼번에 데려다 주기와 1명,1명 각각 데려다 주기를 묶어서 그냥 풀어 버립니다.
[code c++]
int rr(0), a, b;
sort(all(times));
int n = sz(times);
while(n>3) {
a = times[1]+times[0]+times[n-1]+times[1];
b = times[n-1]+times[0]+times[n-2]+times[0];
rr += min(a,b);
n -= 2;
}
if(n==3) { rr += times[n-1] + times[0] + times[1];}
if(n==2) { rr += times[1];}
if(n==1) { rr += times[0]; }
return rr;
[/code]
이러면 속도가 O(n)이 되버리죠.
이럴 경우에 1명,2명,1명,2명,2명...인 경우를 체크하지 못하는데요. 어떤 생각으로 2명 단위로 짤라서 처리해 버렸을까요.
(둘 다 시스템 테스트는 통과합니다)
16년 전