신뢰도 최대화

면접 대비

시간 제한0.5초메모리 제한512 MB

요약

N개의 장식품과 N개의 위치에 대해 신뢰도 행렬이 주어질 때, 각 장식품을 서로 다른 위치에 배치하여 신뢰도의 곱이 최대가 되는 배치를 구해 출력한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 비트 연산, 행렬, 조합론
정답자: 아직 제출이 없습니다

문제

Sicrana는 장식품을 좋아한다. 그녀는 집에 N개의 장식품을 가지고 있고, 이것들은 큰 선반 위에 일렬로 진열되어 있다. 각 장식품은 1과 N 사이의 서로 다른 정수로 식별된다.

어느 날 실내에서 공놀이를 하던 Sicrana의 아들 Fulano가 어머니의 장식품 선반에 공을 맞혀 모든 장식품을 바닥에 떨어뜨렸다. 다행히 떨어지면서 망가진 장식품은 없었다. Fulano가 장식품을 원래대로 정확히 선반에 되돌려 놓으면 어머니는 무슨 일이 있었는지 눈치채지 못할 수도 있다.

Fulano는 기억력이 좋지 않아서 장식품이 원래 어떤 순서였는지 기억하지 못하므로 너의 도움이 필요하다. 각 장식품 i에 대해 Fulano는 1과 100 사이의 N개 숫자를 알려줄 것이고, j번째 값은 i번 장식품이 원래 선반의 j번 위치에 있었을 것이라고 Fulano가 확신하는 정도를 나타낸다. Fulano가 혼나지 않을 것이라는 확신을 최대화하려면, 순서를 정해 장식품을 배치할 때 각 장식품이 제자리에 있을 확신을 곱한다. 더 형식적으로, 주어진 장식품 순서에 대한 Fulano의 총 신뢰도는 다음과 같이 계산된다. pi를 i번 장식품이 차지하는 위치라고 하고 a(i, j)를 i번 장식품이 원래 j번 위치에 있었을 것이라고 Fulano가 확신하는 정도라고 하면, Fulano의 총 신뢰도는 ∏a(i, pi)로 주어진다.

장식품을 배치하는 방법이 너무 많기 때문에, 너의 임무는 Fulano의 총 신뢰도를 최대화하는 순서를 찾는 것이다.

입력

입력의 첫 줄에는 정수 N (1 ≤ N ≤ 100)이 주어지며, 이는 장식품의 개수를 나타낸다. 그다음 N개 줄 각각에는 1과 100 사이의 N개 정수가 주어진다. i번째 줄의 j번째 값은 i번 장식품이 원래 선반의 j번 위치에 있었을 것이라고 Fulano가 확신하는 정도를 나타낸다.

출력

프로그램은 총 신뢰도를 최대화하기 위해 Fulano가 장식품을 배치해야 하는 순서를 나타내는 N개의 정수를 한 줄에 출력해야 한다. 최대 신뢰도를 내는 순서가 여러 개라면, 그중 어느 것을 출력해도 된다.

예제2

예제 1
입력
```
3
1 15 37
42 8 25
77 2 1
```
예상 출력
```
3 1 2
```
예제 2
입력
```
2
15 1
33 42
```
예상 출력
```
1 2
```