간단한 수학 문제인데 못풀었다

[whatugo..(sibal214)]

1. 테스트 케이스 입력

2. A, B, C의 갯수 입력

3. AB, BC, CA의 가격 입력

출력 => A, B, C를 사용(남기지 않고 같은 조건 없음)해서 가장 큰 이익을 내고, 그 이익을 출력

존나 쉬워보이는데 안풀림ㅋㅋ

당연히 ㅄ같은 3중포문쓰면 타임아웃뜹니다

[ㅅㅅㅅ(125.128)]

코세님 오시니까 기다리셨다는 듯이 문제 올리시네요 ㅋㅋㅋ 피자 파티 주최 잼

[whatugonnado(sibal214)]

아무도 반응이 없는걸로 봐서 피자를 내가 걸어야 사람들이 하려나

[whatugonnado(sibal214)]

참고로 문제 링크 :
https://www.acmicpc.net/problem/8901

[익명(222.112)]

1. 제약조건이 있는 최적화 문제로 보고, KKT 컨디션과 라그랑주 메소드를 이용해서 iterative하게 구한다

[익명(222.112)]

2. 루프 2개로 구할 수 있음. BC가 제일 싸니까 AB, AC 조합만 다 따져보면 될듯..? BC는 루프 안쓰고 AB, AC 조합에 따라 알아서 구할 수 있음 (AB, AC에 다 쓰고 남은 B, C로)

[익명(222.112)]

1번은 정수로 딱 떨어지지 않을테니 2번이 답이겠네여

[whatugonnado(sibal214)]

라그랑주승수법은 연속하는 수에만 적용가능한거아님?

[whatugonnado(sibal214)]

댓글다는중에 아니라고 정정댓글달아놨네

[whatugonnado(sibal214)]

가장싼걸 냅두고 딴거부터한다? 근데 그게 ab bc가 가격이같고 ca가 비싸면 그대로 적용이 안될듯?

[익명(222.112)]

가격 모두 다르다면서여

[whatugonnado(sibal214)]

한번 인풋예제 보셈 다 같은 경우도 있는데여

[익명(147.46)]

문제에 가격 다르다고 써있는데여

[익명(147.46)]

B, BC, CA의 가격은 모두 다르다. 따라서, 만드는 화학 제품에 따라서 얻는 이익은 달라진다. 항상 정수 단위 만큼 두 화학 물질을 혼합할 수 있다.

[익명(147.46)]

icpc는 문제를 잘읽는 것이 중요하졈!

[whatugonnado(sibal214)]

같은 물질 이용해도ㅇ가격이 달라질수 없다는 뜻으로 이해했는데 이미 인풋에 100 100 100 넣고도 아웃풋이 나온 상황에...

[whatugonnado(sibal214)]

*달라질 수 있다는 뜻으로

[익명(147.46)]

아 싼거 생각 안해도 두개로만 루프 돌리면될듯? 예를들어서 AB, AC로 루프 돌린다 치면 BC는 알아서 구해지네

[익명(147.46)]

AB, AC 모든 조합을 다 따지면 BC의 모든 조합도 자동으로 탐색함

[whatugonnado(sibal214)]

하나를 메인으로 dfs 돌리고 그걸로 하나가 영향을 받고 다른 하나를 자동으로 ?? 암튼 그렇게 해도 타임아웃 걸릴거 같은 예감이..

[익명(147.46)]

for (i=0; i<(A,B 개수 중 작은 값); i++) { for (j=0; j<(A,C 개수 중 작은 값); j++) { ## BC 개수는 B, C 개수 중 작은 값으로 자동으로 결정됨 ## }}

[whatugonnado(sibal214)]

ㄴ 오 천재야

[whatugonnado(sibal214)]

는 틀렸습니다 ㅠㅠ

[whatugonnado(sibal214)]

는 내가 병신. 고맙다

[whatugonnado(sibal214)]

참고로 위 설명에서 i < min(a,b) 가 아니라 i<= min(a,b)