[백준 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 ≤ N ≤ 100)을 출력합니다.
2. 이후 N−1개의 줄에는 i번째 줄에 N−i개의 정수 A[i][i+1], A[i][i+2],…,A[i][N] (1 ≤ A[i][j] ≤ 100)을 출력합니다.

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

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

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

 

 

 

해설

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

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

그리고 매 레벨마다, sx + px가 i레벨로 이동하는데 드는 코인과 sy + py가 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*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")