1. 문제 N명의 선수를 승부 조작에 참여시켰다. 결승 리그는 여러번의 1:1 경기이다 무승부 없이 항상 승부가 나며 모든 경기가 끝난 후 승수가 가장 많은 선수가 우승한다. 만약 가장 승수가 많은 선수가 둘 이상 있을 겨우 공동 우승을 하게 된다 대부분 우승하지 못할 것으로 여겨지는 X 를 단독 우승하도록해서 이득을 취하려고한다 의심을 피하기위해 가능한 X가 적은 승수로 우승하도록 하고싶다 현재 각 선수의 승수와 남아 있는 경기 목록이 주어질 때. 승부를 적절히 조작해 X가 우승하도록 할 수 있는지 여부를 계산하고, 우승할 수 있다면 필요한 X의 최소 승수는 얼마인지 계산하는 프로그램을 작성하여라. 이때 단독 우승이 불가능할 경우 -1을 출력한다. 그리고 모든 선수가 같은 수의 경기를 치르도록 보장되어..

1. 문제 A나라와 B나라가 경기를 한다고 한다. 이때 종목들과 종목마다 두 나라 선수의 예상 기록이 주어질때 두 나라를 무승부로 만들려고한다. 이때 가장 짧은 기록을 구하는 문제이다. 만약 무승부가 될 수 없으면 IMPOSSIBLE을 출력한다. 2. 책의 풀이: 그래프의 생성 만들수 있는 코스는 무한히 많다. 따라서 완전 탐색으로 이 문제를 풀기 불가능하지만 모든 코스를 다 만들어 봐야하는 것은 아니다. 힌트는 종목들 간의 순서가 상관이 없다는 것이다. 이 문제에서 종목들의 종류나 순서는 중요하지 않다. 의미 있는 것은 두 선수의 예상 시간 차이 뿐이다. 코스에 종목을 하나 추가하면, 그 종목에 따라 차이는 변화한다. 이와 같은 정보를 그래프로 표현하려면 A국 선수의 예상 시간에서 B국 선수의 예상 시..

1. 문제 한 도시에서 다른 도시까지 여행을 하고싶다. 철도망은 여러 개의 역들과 그들을 잇는 노선으로 구성되어 있다. 각 구간별로 철도의 운행 속도가 정해져 있다. 가속과 감속을 반복하면 멀미때문에 괴롭다. 따라서 항상 비슷한 속도로 여행하고싶다. 철도망이 주어질때 여행 구간 중 최대 운행 속도와 최소 운행 속도의 차를 최소화하는 경로를 찾는 프로그램을 작성하라 시작 철도역은 항상 0 번이고 도착할 철도역은 항상 N-1번이다. 2. 책의 풀이1 어떤 경로에서 모든 간선의 가중치가 어떤 값 U이거나 그보다 작을 때, U를 '상한'이라고 하고 반대로 모든 간선의 가중치가 어떤 값 L이거나 그보다 클 때, L을 이 경로의 '하한'이라고 하자. 경로의 최소 상한과 최대 하한의 차이를 경로의 '너비'라고 하면 ..

1. 문제 새로 건설할 당위성이 있다: 고속도로를 통해 오갈 수 없던 두 도시가 새로 연결됨. 두 도시를 오가는 데 걸리는 시간이 단축 되어야함 N년간 하나씩 고속도로를 건설할때 이들 중 몇 개가 의미가 없는지 계산하여라 2. 플로이드 n번 역시 간단한 풀이는 그냥 건설할때마다 플로이드를 수행하는 것이다, 하지만 이는 시간초과로 문제를 시간안에 해결할 수 없다. 또다른 방법은 플로이드를 계산할때 a, b 정점을 경유하는지 기록하는 것 만약 고속도로가 추가되면 이 기록을따라 a->b, b->a거리를 업데이트 시키고, b와 a에 대해서만 플로이드를 다시 수행하는 것이다. 하지만 이것은 구현도 까다롭고 복잡하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ..

1. 문제 C개의 선물들을 n명의 아이들에게 나누어주는데 m명의 아이들에게는 1+ g 개 n-m 명의 아이들에게는 g개 씩 나누어준다고한다. 이때 C는 D 목록에 있는 수로만 이루어져있는 자연수여야한다. 2. C의 성질 이 문제는 D목록을 정점으로하는 무향 그래프를 생성하여 0에서부터(impossible) bfs로 차근차근 하나씩 자리수를 늘려가며 맞아 떨어지는지 검사하는 문제인것같다 문제에서 주어지는 변수들로 수학식을 정리해보면 다음과 같다 C = m(1+g) + (n-m)g C = ng + m C%n = m%n (C>=n) C%n = m ,,, m>n 즉 목록 D로 구성되어있는 C를 n으로 나눈 나머지는 m을 n으로 나눈 나머지와 같아야한다 이때 m과 n은 고정점이므로 이점을 이용하면 목록이 주어졌을..

1. 회의실 배정 문제 이 문제는 n개의 팀이 회의를 할 수 있는 두 시간 범위가 주어지고 두 시간중 한 타임을 선택하여 모든 팀이 회의를 할 수 있게하는 문제이다. 2. 그래프 만들기? 그래프의 정점들은 각 시간의 첫부분과 끝부분이어야 할 것 같다. 그러면 간선은 회의를 하는 시간을 표현해야할 꺼 같다. 각 회의 구간은 겹칠수 있다. A -> B A->a->b->B C -> D 위와 같은 다양한 경우가 존재할 수 있다. 어떻게 그래프를 표현해야할까 인접행렬로 표현할 시 시간의 범위가 43200이므로 메모리가 432000*432000로 1억이 넘어가므로 이건 아닌거 같다. 인접리스트로 각 시간을 담는것도 조금 무리인것 같지만 행렬보다는 아니다. 시간을 겹치는 것끼리 같은 그룹으로 묶어서 압축을 시키면 어..