[완료]알고리즘 문제 해결 좀 해주세요.
글쓴이: kldpjasm / 작성시간: 금, 2012/03/23 - 12:42오전
ㅠㅠ 미치겠네여 쉬운듯 하면서도 못풀고 있습니다.. 아..
미숫가루가 있으면 3kg 자루와 5kg 자루에다가 포장 해야 합니다. 여기서 1kg이상 남으면 fail을 출력 합니다.
input..계산....output
7 ..... 3x2 ...... fail(1kg이 남음)
12 ... 3x4 ...... 4자루
13 ... 5x2,3x1 3자루
16 ... 5x2,3x2 4자루
아아.. 개발자에 역량이 너무 부족 한가 봅니다. 여틋보면 쉬우면서도 막상 120분 시간이 주어지니까 풀수가 없네요.
도와주세요
[완료]다들 감사합니다;;
역시나 프로그래밍은 언어보단 문제 해결능력이 더 중요하다는 걸 몸소 느낍니다.
다들 나서서 도와주신거 정말 고마워용~
마지막으로 알고리즘 관련된 서적이나.. 꼭 봐야할 지식 같은게 있으시면 알려주세요~
Forums:
선형계획법
선형계획법 문제군요
http://ko.wikipedia.org/wiki/%EC%84%A0%ED%98%95_%EA%B3%84%ED%9A%8D%EB%B2%95
정수 영역에서 풀어야 한다는 것만 조심하면 되겠네요.
y=3i+5j를 만족하는 (i>=0,j>=0)의 정수 쌍을 찾아야 하는 문제가 되니까, y=3i+5j를 만족하고 이 직선의 x절편과 y절편 사이의 1사분면에서 가능한 i, j값에 대해서 전부 검사해보면 되겠죠.
피할 수 있을때 즐겨라! http://melotopia.net/b
5가지 경우만 검사하면 됩니다. 3kg 자루를
5가지 경우만 검사하면 됩니다.
3kg 자루를 (0,1,2,3,4}개 쓰는 경우.
익명님 댓글을 보고나니 이렇게 풀 수
익명님 댓글을 보고나니 이렇게 풀 수 있겠군요
n%5=0, 1, 2, 3, 4중의 하나겠죠
0이면 그냥 OK
1이면 n이 6보다 큰 경우면 OK (5로 나눈 나머지가 1이면, 6보다 크면, 끝에 6을 남길 수 있으므로)
2이면 n이 12보다 큰 경우면 OK (5로 나눈 나머지가 2이면, 12보다 크면, 끝에 12를 남길 수 있으므로)
3이면 그냥 OK
4이면 n이 9보다 큰 경우면 OK (5로 나눈 나머지가 4이면, 9보다 크면, 끝에 9를 남길 수 있으므로)
따라서 다음의 알고리즘으로 풀면 됩니다.
if (n>12) then return TRUE
else if n in {0, 3, 5, 6, 8, 9, 10, 12} then return TRUE
else return FAIL
그 다음, 위에서 TRUE인 경우에만
if n%5==0 then return n/5
if n%5==1 then return n/5+1
if n%5==2 then return n/5+2
if n%5==3 then return n/5+1
if n%5==4 then return n/5+2
피할 수 있을때 즐겨라! http://melotopia.net/b
그러고보니, 그냥 n<0 or n=1, 2, 4,
그러고보니, 그냥 n<0 or n=1, 2, 4, 7, 11이면 fail이네요 -_-
그리고 끝의 조건문들은 (n/5)+((n%5)/3)+((n%5)%3)로 한번에 쓸 수 있겠네요. 나눗셈은 정수만 몫으로 나오는 정수 나눗셈입니다.
if not(n<0 or n==1 or n==2 or n==4 or n==7 or n==11)
then return (n/5)+((n%5)/3)+((n%5)%3)
else return FALSE
이렇게 출력하면 되겠네요
피할 수 있을때 즐겨라! http://melotopia.net/b
아 11은 빼야겠네요 -_-
아 11은 빼야겠네요 -_-
피할 수 있을때 즐겨라! http://melotopia.net/b
그렇게 따지면 안되죠. input에 넣을 값을 미리 정해놓으면 저도 풀겠습니다;
input에 들어갈 값을 10단위가 아니라 제한 없이 들어갑니다;
즉 100 이 들어갈수도 있고 145가 들어갈수도 있어요;
14가 끝이 아니라 그냥 예시를 해드린거에요 ㅠ
KLDP에서 분명 풀어줄꺼라 생각했는데 여기 나온 답변들 다 C로 풀어서 컴파일 해봤지만 17값을 넣으면 5가 아웃풋 되버리고 그러네요.
흐...
제 방법은 임의의 n에 대해서 잘 작동한다고
제 방법은 임의의 n에 대해서 잘 작동한다고 생각합니다.
예를 들어서 n=17을 넣으면
(n/5)+((n%5)/3)+((n%5)%3)
n/5=3
n%5=2
2/3=0
2%5=2
3+2=5
5kg짜리 자루 1개, 3kg짜리 자루 4개로 채우면 되므로 5개 맞습니다.
5kg짜리 자루가 몇개인지, 3kg짜리 자루가 몇개인지 알고 싶다면 다음과 같이 하면 됩니다.
n%5=0이면 5kg짜리가 n/5개, 3kg짜리가 0개
n%5=1이면 5kg짜리가 (n/5)-1개, 3kg짜리가 2개
n%5=2이면 5kg짜리가 (n/5)-2개, 3kg짜리가 4개
n%5=3이면 5kg짜리가 n/5개, 3kg짜리가 1개
n%5=4이면 5kg짜리가 (n/5)-1개, 3kg짜리가 3개
필요합니다.
이거에 대해서 3kg짜리가 몇개 필요한지 리턴하는 함수는
(n%5)*2)%3
이고
전체 갯수와 3kg짜리 갯수를 알고 있으므로 5kg짜리가 몇개 필요한지는
(n/5)+((n%5)/3)+((n%5)%3)-((n%5)*2)%3)
이 됩니다.
어디가 틀렸는지 알고 싶어요. ㅜㅜ
피할 수 있을때 즐겨라! http://melotopia.net/b
아, 여기서 임의의 n은 n=1, 2, 4, 7이
아, 여기서 임의의 n은 n=1, 2, 4, 7이 아닌 경우만 해당합니다. 즉, 1, 2, 4, 7만 아니면 위의 루틴으로 다 풀 수 있다고 생각합니다.
증명도 해놔야 하는걸까요...-_-
피할 수 있을때 즐겨라! http://melotopia.net/b
아 그렇군여.. 제가 착각을 했네요.
17인 경우도 5x1, 3x4 5자루가 되는군여;;;
네이버에도 물어보니 갈켜주더군요 ㅠ
으아아아아ㅏ 난 왜 알고리즘을 못하는거징
#include
int main(int argc, char *argv[]) {
int weight;
int box5s = 0;
int box3s = 0;
int total;
int remainder;
// 1. 무게를 입력받는다.
scanf("%d", &weight);
remainder = weight;
// 2. 5kg자루에 담을 수 있는 동안 반복한다.
while(remainder >=5 ) {
// 2.1. 5kg자루를 담는다.
box5s++;
remainder -= 5;
}
// 3. 설탕이 남아 있는 동안 반복한다.
while(box5s >= 0 && remainder != 0) {
//3.1. 3kg 자루에 담을 수 없으면
if(remainder < 3) {
// 3.1.1. 5kg 자루를 붓는다.
box5s--;
remainder += 5;
}
// 3.2. 3kg 자루를 담는다.
box3s++;
remainder -= 3;
}
// 4. 전체 자루수를 센다.
if(remainder != 0) {
box5s = 0;
box3s = 0;
}
total = box5s + box3s;
// 5. 5kg자루의 개수, 3kg 자루의 개수 그리고 전체 자루수의 개수를 출력한다.
printf("5kg : %d 3kg : %d 전체 : %d\n", box5s, box3s, total);
// 6. 끝낸다.
return 0;
}
5로 나눈 나머지가 3이나 0이면 ... OK
이건 아니죠..
============================================================
선한 인간이냐 악한 인간이냐는 그사람의 의지에 달렸다. -에픽테토스-
의지 노력 기다림은 성공의 주춧돌이다. -파스퇴르-
============================================================
아메바 수준의로 써놓았네요..
ㅎㅎ
============================================================
선한 인간이냐 악한 인간이냐는 그사람의 의지에 달렸다. -에픽테토스-
의지 노력 기다림은 성공의 주춧돌이다. -파스퇴르-
============================================================
제가 틀렸나요?
제가 틀렸나요?
피할 수 있을때 즐겨라! http://melotopia.net/b
대충 이렇게 풀면..
if (in%5==0) {
printf("%d\n", in/5);
} else if (in%3==0) {
printf("%d\n", in/3);
} else {
int n5, n3, sum=0;
n5 = in/5;
n3 = in/3;
for(int i=0; i<=n5; i++) {
for(int j=0; j<=n3; j++) {
sum = i*5+j*3;
if (sum > in) continue;
if (sum == in) {
printf("%d\n", i+j);
return 0;
}
}
}
printf("fail\n");
}
되지않을까요.
와 풀렸네요.
ㅜㅜ 이렇게 푸는거군요. 아 알고리즘 공부 열심히 해둘껄..ㅠ
#include
int main(){
int in;
scanf("%d",&in);
if (in%5==0) {
printf("%d\n", in/5);
} else if (in%3==0) {
printf("%d\n", in/3);
} else {
int n5, n3, sum=0;
n5 = in/5;
n3 = in/3;
for(int i=0; i<=n5; i++) {
for(int j=0; j<=n3; j++) {
sum = i*5+j*3;
if (sum > in) continue;
if (sum == in) {
printf("%d\n", i+j);
return 0;
}
}
}
printf("fail\n");
}
}
읔.. 풀린듯 싶었는데 아니네영.
17값을 주면 fail이 나와야 하능데.. 안나오네요.
5kg 이랑 3kg 자루만 써야 하니까..
맞지않나요?
3kg 4개 쓰고, 5kg 1개쓰면 되지요.
두번째 댓글 단 사람입니다. 일반적으로 확장하면
두번째 댓글 단 사람입니다.
일반적으로 확장하면 선형계획법으로 풀어도 되긴 합니다만 코딩하기가 너무 어려워요. ㅠㅠ
심플렉스 알고리즘을 버그 없이 120분 내로 코딩하는 건 많이 어렵겠죠. 전 당연히 못하고요.
15kg 같으면 3kg * 5도 되고, 5kg * 3도 되잖아요. 그러니까 3kg짜리를 5개 이상 쓸 필요는 없어요.
문제 조건에 명시되지는 않았지만 기왕이면 자루를 적게 쓰는게 좋잖아요.
그래서 3kg을 {0,1,2,3,4}개 쓰고 조건을 맞출 수 있나 검사하면 되어요.
그런데 이걸 검사하려면 x-{0,1,2,3,4} % 5를 해야하니 좀 귀찮긴 하네요.
그래서 snowall님의 방법대로 x%5를 보고 분류하면 됩니다. (사실 두 방법의 각 case가 대응됩니다.)
switch(x%5) {
case 0: // 3kg 자루를 0개 쓰면 되죠.
return x/5;
case 1: // 3kg 자루를 2개 쓰면 되죠.
if (x < 6) return "fail";
return (x-6)/5 + 2
case 2: // 3kg 자루를 4개 쓰면 되죠.
if (x < 12) return "fail";
return (x-12)/5 + 2
case 3: // 3kg 자루를 1개 쓰면 되죠.
if (x < 3) return "fail";
return (x-3)/5 + 1
case 4: // 3kg 자루를 3개 쓰면 되죠.
if (x < 9) return "fail";
return (x-9)/5 + 3
}
그리고 (x-9)/5 + 3같은 건 x/5 + 2로 바꾸는 거죠. (x%5==4인걸 아니까 치환 가능한 겁니다.)
결론적으로 snowall님 코드는 맞는 것 같은데요?
xyhan님은 어디가 틀렸다고 생각하시는지요...
아무튼 3과 5처럼 고정된 수가 주어졌을 때 문제를 푸는 건 비교적 쉽고, 임의의 a, b가 주어졌을 때 같은 문제를 풀어보면 재미있겠군요.
begin{signature}
THIS IS SPARTA!!!!!n.
end{signature}
dynamic programming(동적계획법)
저는 이 문제를 dynamic programming(동적계획법)으로 접근해보았습니다.
먼저 표기법부터 정의하면,
f(n) : n kg 을 포장하는 방법 (딱 떨어지게 포장 못하면 fail, 포장이 가능하면 가장 적은 자루 수를 반환)
자루의 무게 종류는 (뒤에서 좀 더 일반적인 상황으로 풀어보겠습니다만,)
질문자께서 말씀하신 3 kg, 5 kg 두 가지만 있다고 가정하겠습니다.
점화식을 세우면 다음과 같습니다
f(3) = 1, f(5) = 1
f(x) = min(f(x-3), f(x-5)) + 1
첫 번째 줄은 명백하게 가장 최소한의 자루 수를 반환한 것이고요. (base 라고 부르겠습니다.)
두 번째 줄은 f(x)의 답은 f(x-3)의 답에서 3kg 하나 더 추가한 것과 f(x-5)의 답에서 5kg 하나 더 추가한 것 중에서
적은 쪽을 선택하겠다는 의미입니다.
실제로 n 을 0에서 부터 풀어보겠습니다.
f(0) = fail
f(1) = fail
f(2) = fail
f(3) =1자루 (3x1, 5x0)
f(4) = fail
f(5) =1자루 (3x0, 5x1)
여기까지 첨에 구한 base가 다 나왔죠.
그 다음부터는
f(6) = min(f(3), f(1)) + 1
여기서 f(1)은 fail 이므로 fail의 경우는 무한 개의 자루를 썼다고 가정하고 f(3)+1 의 값이 f(6)의 답이 됩니다.
즉,
f(6) = min(f(3), f(1)) + 1 = f(3) + 1 = 2자루 (3x2, 5x0)
f(7) = min(f(4), f(2)) + 1 = fail
f(8) = min(f(5), f(3)) + 1 = f(5) + 1 = 2자루 (3x1, 5x1) <- 여기서 f(5)+1 대신에 f(3)+1을 취해도 결과는 같습니다. 이유는 3 kg을 먼저 넣고 5 kg 넣거나 그 반대로 해도 같기 때문이죠.
f(9) = min(f(6), f(4)) + 1 = f(6) + 1 = 3자루 (3x3, 5x0)
이렇게 점화식을 따라가면 일반적인 n에 대해서 f(n)을 풀 수 있습니다.
그리고 이 문제는 사실 좀 더 일반화 된 버전으로 확장 가능한데요.
질문자께서는 자루의 무게 종류가 3 kg, 5 kg 두 가지만 있다고 하셨는데
일반화 버전은 자루의 무게 종류도 2개 이상 여러개가 될 수 있다고 확장할 수 있습니다.
예를 들어 3 kg, 5 kg, 8 kg 세 가지가 있다고 보면,
점화식을 다음과 같이 세울 수 있죠.
f(3) = 1, f(5) = 1, f(8) = 1
f(x) = min(f(x-3), f(x-5), f(x-8)) + 1
이전과 어떻게 달라졌는지 비교해 보시길 바랍니다.
이것도 실제로 n 을 0에서 부터 풀어보겠습니다.
f(0) = fail
f(1) = fail
f(2) = fail
f(3) =1자루 (3x1, 5x0, 8x0)
f(4) = fail
f(5) =1자루 (3x0, 5x1, 8x0)
/* 아직 base 가 3 kg, 5 kg 까지만 나왔음 */
f(6) = min(f(3), f(1)) + 1 = f(3) + 1 = 2자루 (3x2, 5x0, 8x0)
f(7) = min(f(4), f(2)) + 1 = fail
f(8) = 1자루 (3x0, 5x0, 8x1)
/* 여기서부터는 base가 모두 나옴 */
f(9) = min(f(6), f(4), f(1)) + 1 = 3자루 (3x3, 5x0, 8x0)
f(10) = min(f(7), f(5), f(2)) + 1 = 2자루 (3x0, 5x2, 8x0)
f(11) = min(f(8), f(6), f(3)) + 1 = 2자루 (3x1, 5x0, 8x1)
..
아래 제가 짠 코드를 올려드립니다.
먼저 3 kg, 5 kg 만 있을 경우
#include <stdio.h> #define N 1000 #define M 2 #define FAIL 9999 int Weight[M]; // weight of each package int Count[N][M]; // a number of each package for 'N' kg int Total[N]; // a total number of packages for 'N' kg void init(); int main(int argc, char** argv) { init(); // solve for (int i=0; i<N; ++i) { for (int j=0; j<M; ++j) { int pre = i - Weight[j]; if (pre < 0) { // out of range continue; } if (Total[pre] == FAIL) { // the previous result is FAIL // 'Total[i]' cannot be calculated from 'Total[pre]' continue; } if (Total[i] > Total[pre]) { // update with smaller previous result Total[i] = Total[pre] + 1; for (int k=0; k<M; ++k) { Count[i][k] = Count[pre][k]; } Count[i][j]++; } } } // print the first 29 results for (int i=1; i<30; ++i) { if (Total[i] == FAIL) { printf("%4d ... fail\n", i); continue; } printf("%4d ... ", i); for (int j=0; j<M; ++j) { printf("%dx%d, ", Weight[j], Count[i][j]); } printf("(total: %d)\n", Total[i]); } return 0; } void init() { Weight[0] = 3; Weight[1] = 5; for (int i=0; i<N; ++i) { Total[i] = FAIL; } // solve bases for (int i=0; i<M; ++i) { Total[Weight[i]] = 1; Count[Weight[i]][i] = 1; } }3 kg, 5 kg, 8 kg 로 확장할 경우엔 M 의 값을 3으로 하고 init 함수에서 8 kg 부분을 추가하면 됩니다.
#include <stdio.h> #define N 1000 #define M 3 #define FAIL 9999 int Weight[M]; // weight of each package int Count[N][M]; // a number of each package for 'N' kg int Total[N]; // a total number of packages for 'N' kg void init(); int main(int argc, char** argv) { init(); // solve for (int i=0; i<N; ++i) { for (int j=0; j<M; ++j) { int pre = i - Weight[j]; if (pre < 0) { // out of range continue; } if (Total[pre] == FAIL) { // the previous result is FAIL // 'Total[i]' cannot be calculated from 'Total[pre]' continue; } if (Total[i] > Total[pre]) { // update with smaller previous result Total[i] = Total[pre] + 1; for (int k=0; k<M; ++k) { Count[i][k] = Count[pre][k]; } Count[i][j]++; } } } // print the first 29 results for (int i=1; i<30; ++i) { if (Total[i] == FAIL) { printf("%4d ... fail\n", i); continue; } printf("%4d ... ", i); for (int j=0; j<M; ++j) { printf("%dx%d, ", Weight[j], Count[i][j]); } printf("(total: %d)\n", Total[i]); } return 0; } void init() { Weight[0] = 3; Weight[1] = 5; Weight[2] = 8; for (int i=0; i<N; ++i) { Total[i] = FAIL; } // solve bases for (int i=0; i<M; ++i) { Total[Weight[i]] = 1; Count[Weight[i]][i] = 1; } }도움이 되셨길 빕니다.
댓글 달기