[백준 19631] Wrong Answer

티어: 플2

문제 지문이 영어로 되어 있어 한국어로 번역한 내용을 첨부합니다.

문제#

트로이는 프로그래밍 대회를 위해 "WA"라는 제목의 문제를 만들었습니다. 그 문제는 다음과 같습니다.

게임에는 1번부터 $N$번까지 번호가 매겨진 $N$개의 레벨이 있습니다. 두 캐릭터가 있으며, 두 캐릭터 모두 처음에는 1번 레벨에 있습니다.

$i < j$인 경우, 캐릭터를 $i$번 레벨에서 $j$번 레벨로 이동시키는 데는 $A[i][j]$ 코인이 듭니다. $i > j$인 경우 이동할 수 없습니다.

게임에서 승리하려면, 1번 레벨을 제외한 모든 레벨을 정확히 한 캐릭터가 방문해야 합니다. 이때 필요한 최소 코인의 수는 얼마입니까?

JP는 이 문제를 해결하기 위해 아래와 같은 Python 코드를 제출했습니다:

def Solve(N, A):
    # A[i][j]: 레벨 i에서 j로 이동하는 비용
    # N: 레벨 수
    x, y, sx, sy = 1, 1, 0, 0  # x와 y를 1로 초기화, sx와 sy를 0으로 초기화
    for i in range(2, N + 1):  # 2부터 N까지 반복
        if sx + A[x][i] < sy + A[y][i]:
            sx += A[x][i]
            x = i
        else:
            sy += A[y][i]
            y = i
    return sx + sy

트로이는 JP의 풀이가 잘못되었다고 확신합니다. 예를 들어, 특정 입력 $N$과 $A[i][j]$에 대해 JP의 풀이가 $X$를 반환했지만, 실제 최소 코인 수가 $Y$라고 가정합시다. JP의 풀이가 얼마나 잘못되었는지를 보여주기 위해, $X / Y$를 최대화하는 입력을 찾아야 합니다.

입력#

입력은 없습니다.

출력#

다음과 같은 형식으로 WA의 입력을 출력하세요:

1. 첫 번째 줄에 정수 $N$ ($2 \le N \le 100$)을 출력합니다.
2. 이후 $N - 1$개의 줄에는 $i$번째 줄에 $N - i$개의 정수 $A[i][i+1], A[i][i+2], \ldots, A[i][N]$ ($1 \le A[i][j] \le 100$)을 출력합니다.

출력이 올바르지 않은 형식이라면 0점이 부여됩니다.

출력이 올바른 형식이라면, JP의 풀이 결과 $X$와 실제 최소 코인 수 $Y$에 대해 $X / (4Y)$ 포인트를 받게 됩니다.

24점 이상을 획득해야 ac를 받습니다.

해설#

JP의 알고리즘을 분석해보면 허점을 찾아낼 수 있다. 두 캐릭터를 각각 $px$, $py$라고 하자.

$x$, $y$에는 $px$, $py$가 현재 위치한 레벨이 들어 있고, $sx$, $sy$에는 $px$, $py$가 지금까지 사용한 코인 개수가 들어 있다.

그리고 매 레벨마다, $px$가 $i$레벨로 이동하는 데 드는 코인을 더한 $sx + A[x][i]$와 $py$가 $i$레벨로 이동하는 데 드는 코인을 더한 $sy + A[y][i]$를 비교해 더 적은 쪽을 선택한다.

if문을 보면 조건이 $sx + A[x][i] < sy + A[y][i]$로 되어 있는데, 여기서 2가지 허점을 발견할 수 있다.

1. 캐릭터가 지금까지 사용한 코인 개수가 현재 레벨 선택에 영향을 미친다. 즉, $A[x][i]$와 $A[y][i]$의 대소로 판단하는 것이 아니다.
2. 좌변과 우변이 같다면 무조건 $py$를 이동한다.

이제 이 허점을 이용해서 입력값을 만들어보자.

전략은 다음과 같다.

• 초기 단계에서, 두 캐릭터가 이동하는 비용을 같게 만든다. 이는 최소 비용을 달성하려면 $px$가 이동해야 하지만, JP의 허점으로 인해 $py$가 이동하는 것을 유도하기 위함이다.
• 이후 JP가 가게 되는 모든 선택지의 비용을 100으로 한다. 최적의 경로는 비용이 1이지만, JP는 선택할 수 없도록 한다.

자명하게도 $A[1][2]$는 무조건 사용된다. 이 비용을 1로 정하자.

JP의 알고리즘에선 2번 허점에 따라 $py$를 1번 레벨에서 2번 레벨로 이동시킨다.

3번 레벨에서, JP의 알고리즘은 $0 + A[1][3] < 1 + A[2][3]$이라는 조건에 따라 캐릭터를 선택하게 될 것이다.

1번 허점을 이용해 $A[1][3] = A[2][3] = 1$로 정하면, JP의 알고리즘은 $px$를 1번 레벨에서 3번 레벨로 이동시킨다.

여기서 우리는 함정을 판 것이다. $A[1][4] = 1$로 정하고, $A[2][4] = A[3][4] = 100$으로 정하자.

JP의 알고리즘에선 4번 레벨로 이동하는 선택지가 모두 100이라는 비용이 들게 된다.

JP의 알고리즘은 $1 + 100 < 1 + 100$이라는 최악의 조건이 만들어지고, 2번 허점에 의해 $py$를 2레벨에서 4레벨로 이동한다.

여기서 최적의 경로는 $py$가 1번, 2번, 3번 레벨을 순서대로 방문하고, $px$가 1번 레벨에서 4번 레벨로 이동하는 것이 된다.

이후 JP의 알고리즘은 $sx$와 $sy$에 의해 $px$, $py$를 번갈아서 이동하게 된다. 설사 이동하는 비용이 1인 선택지가 있더라도, $sx$와 $sy$는 항상 100씩 차이가 나며 2번 허점에 의해 같다면 $py$를 움직이게 되는 제약이 생긴다.

이렇게 $N = 100$으로 확장시켜 최적의 경로는 1만 따라가게 하고, JP는 100만 따라가게 하면 $X = 9702$, $Y = 99$인 입력값을 만들 수 있다. 이것을 제출하면 $9702 / (4 \times 99) = 24.5$점을 받으며, ac를 받을 수 있다.

c=console.log
c("100\n1 1 1 "+"100 ".repeat(96))
for(i=97;i>2;i-=2)c(`1 ${"100 ".repeat(i)}\n100 100 1 ${"100 ".repeat(i-3)}`)
c("1 100\n100")