본문 바로가기

알고리즘/더블릿5

[더블릿] Koi_Budget 더블릿의 예산 문제 http://59.23.113.171/pool/koi_budget/koi_budget.php?pname=koi_budget 프로그램 명: koi_budget제한시간: 1 초국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.(1) 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.(2) 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정.. 2016. 7. 5.
[더블릿] Koi_Delivery 배송 문제 더블릿의 배송 문제는 다음과 같이 해결한다. 위와 같은 경우입니다. 답은 150인데, 현재 소스는 120을 출력하고 있습니다. 즉, 처음 선택할때 1 6 40에 해당하는 40에서 30만큼을 선택하기 때문에 끝날때까지 택배 가방(님이 가방으로 표현하셔서 그렇게 얘기하겠습니다 ㅋ) 용량이 30으로 밖에 유지될 수 없어서 중간에 크게 옮겨실어나를수 있음에도 불구하고 계속 용량 30밖에 못사용하는거죠. 그럼 어떻게 하냐... s에서 택배꾸러미를 받아서 e에서 택배를 내려놓는다고 할때 s에서부터 e-1까지 해당 택배꾸러미를 계속 들고 있어야 합니다. (e는 내려놓는곳이니까 제외하죠) 해당 택배꾸러미의 용량을 w라고 하면 s부터 e까지는 택배를 기본 여유용량 C에서 w만큼 뺀 것입니다. 즉, 예를 들면 원래 가방용.. 2016. 7. 4.
[더블릿] Koi_Bal 저울 문제 문제 바로가기 저울 문제는 물건의 비교값이 있는 부분을 X 축 기준으로는 작은값, Y축 기준으로는 큰값로 생각하고 배열을 DFS로 확인하여 값을 알 수 있는 데이터를 비교한다. 단방향 간선 그래프, DFS, 이미 방문한 곳은 방문하지 않는다. 이것이 요점사항 인 것 같다. 2016. 7. 2.
[더블릿] 자리 배정 알고리즘(Koi_Seat) 더블릿, 자리배정 알고리즘 문제 순서대로 이동하면서 값을 매겨서 자리를 확인한다. 2016. 6. 28.
[더블릿] 줄세우기 알고리즘(Koi_Align) 줄세우기 알고리즘 해결방법은 다음과 같다. 줄을 세울때 맨 앞과 맨뒤로만 보낼수 있기 때문에, 순서대로 읽어 가면서 정렬이 되어 있는 상태의 숫자는 옮기지 않아도 된다. 정렬이 되어 있지 않은 데이터중 1은 맨앞으로 옮기고, 나머지는 순서대로 맨뒤로 옮기면 자동으로 정렬이 되게 된다. 5, 2, 4, 1, 3의 경우 2, 3은 순서대로 정렬이 되기 때문에 이를 제외한 나머지 값을 옮기게 되므로 5-2 = 3으로 3번 움직여야 한다. 5, 2, 3, 4, 7, 1, 6의 경우 2, 3, 4는 순서대로 정렬 되기 때문에 이를 제외한 나머지 값을 옮기게 되므로 7-3 = 4로 4번 움직여야 한다. 이를 처리하는 코드는 다음과 같다. 2016. 6. 27.

티스토리툴바