No older revisions available
No older revisions available
소감 ¶
일종의 산수문제 같기도 하고,
수식을 생각하는것은 어렵지 않았지만
프로그램의 실행시간을 줄이는데 시간이 들었다.
프로그램은 다음과 같은 원리로 동작한다.
ex)
43
1 3 -> 개당수납비용이 최소
2 4
일때 n = bq+r 이용
43 = 14*3+1 = 3333333333333+3+1 = 3333333333333+4 => 13, 1
수식을 생각하는것은 어렵지 않았지만
프로그램의 실행시간을 줄이는데 시간이 들었다.
프로그램은 다음과 같은 원리로 동작한다.
ex)
43
1 3 -> 개당수납비용이 최소
2 4
일때 n = bq+r 이용
43 = 14*3+1 = 3333333333333+3+1 = 3333333333333+4 => 13, 1
35
1 5 -> 개당수납비용이 최소
20 7
일때
35 = 7*5+0 = 5555555+0 =>7, 0
1 5 -> 개당수납비용이 최소
20 7
일때
35 = 7*5+0 = 5555555+0 =>7, 0
<수정 05 05 15>
이 프로그램의 약점은 n2의 크기가 커지면 실행시간이 늘어난다는 점이다.
n2가 작은 수라면 금방 끝나지만 다음과 같은 worst case일때는 약 몇억번의 루프를 돌아야 한다.
2000000000
1 3
1900000000 1900000000
그 점을 수정하여 굉장히 빠른 속도로 처리 가능하게 함. 덕분에 코드가 복잡해짐;;
아.. 수정후 버그속출 ㅠㅠ
이 프로그램의 약점은 n2의 크기가 커지면 실행시간이 늘어난다는 점이다.
n2가 작은 수라면 금방 끝나지만 다음과 같은 worst case일때는 약 몇억번의 루프를 돌아야 한다.
2000000000
1 3
1900000000 1900000000
그 점을 수정하여 굉장히 빠른 속도로 처리 가능하게 함. 덕분에 코드가 복잡해짐;;
아.. 수정후 버그속출 ㅠㅠ
코드 ¶
~cpp #include <iostream> using namespace std; void main(){ int N[100], n1[100], c1[100], n2[100], c2[100]; int tot_arr = 0; for(int i=0;i<100;i++){ cin >> N[i]; if(N[i] == 0) break; cin >> c1[i]>> n1[i]>> c2[i] >> n2[i]; tot_arr++; } for(i=0;i<tot_arr;i++){ if(c1[i]/(double)n1[i] > c2[i]/(double)n2[i]) //n1에 개당수납비용이 최소인 상자가 오게함. swap(n1[i],n2[i]); int r = N[i]%n1[i]; int m1 = N[i]/n1[i]; int m2 = -1; for(int k=0; k<=n2[i] ;k++){ if(r%n2[i]==0){ m2=r/n2[i]; cout <<n1[i]<<"들이박스 "<<m1<<"개 필요 "<<n2[i]<<"들이박스 "<<m2<<"개 필요 "<<"\n"; break; } r = ((n2[i]/n1[i]==0?1:n2[i]/n1[i])*k+1)*n1[i] + (N[i]%n1[i]); //r은 n2보다 큰 가장 작은 n1의 배수에 N[i]%n1[i]을 더한 값. if(r-n2[i]>=n1[i]) r-=n1[i]; if(r>N[i] || r<0){ int tempk; if(n2[i]*k>N[i]) tempk = k-1; else tempk = k; if((N[i]-n2[i]*tempk)%n1[i] == 0) r = n2[i]*tempk; else break; } m1=(N[i]-r)/n1[i]; } if(m2 == -1) cout << "failed\n"; cout <<"total " << k << " roops\n"; } }
수정 전
~cpp #include <iostream> using namespace std; void main(){ int N[100], n1[100], c1[100], n2[100], c2[100]; int tot_arr = 0; for(int i=0;i<100;i++){ cin >> N[i]; if(N[i] == 0) break; cin >> c1[i]>> n1[i]>> c2[i] >> n2[i]; tot_arr++; } for(i=0;i<tot_arr;i++){ if(c1[i]/(double)n1[i] > c2[i]/(double)n2[i]) //n1에 개당수납비용이 최소인 상자가 오게함. swap(n1[i],n2[i]); int r = N[i]%n1[i]; int m1 = N[i]/n1[i]; int m2 = -1; for(int roop=0; roop<=n2[i] ; roop++){ //루프는 n2만큼 돌린다. 아래에서 r에 n1이 n2만큼 더해지면 n2*n1+r이 되며 //이는 (n2*n1+r)%n2 == r%n2가 되기 때문에 roop=n2이후부터는 이전것의 순환이 된다. if(r%n2[i]==0){ m2=r/n2[i]; cout <<n1[i]<<"들이박스 "<<m1<<"개 필요 "<<n2[i]<<"들이박스 "<<m2<<"개 필요 "<<"\n"; break; } r+=n1[i]; m1--; } if(m2 == -1) cout << "failed\n"; } }