BOJ 34010 - e-코너 시스템 테스트 (Easy)

문제 링크

• https://www.acmicpc.net/problem/34010

문제 요약

$N\times N$ 크기의 2차원 격자에서 $(1,1)$ 출발지부터 $(N,N)$ 도착지까지 이동합니다.

각 격자에서 상하좌우 인접한 격자로만 이동할 수 있으며, 모든 도로의 길이는 1입니다. (이 문제에서는 모든 도로의 길이가 1임이 중요합니다.)

가로 방향으로 이동하다 세로 방향으로 이동하거나, 세로 방향으로 이동하다 가로 방향으로 이동하는 경우 피봇턴을 1회 수행합니다.

목표는 최단 경로로 주행하면서 피봇턴을 가능한 한 많이 수행하는 것입니다. 총 주행 거리와 피봇턴 수행 횟수를 출력해야 합니다.

풀이

이 문제는 최단 경로를 유지하면서 특정 조건을 최대로 만족시키는 문제입니다.

1. 최단 거리 계산: $N\times N$ 격자에서 $(1,1)$에서 $(N,N)$까지 이동하는 최단 경로는 항상 오른쪽으로 $N-1$번, 아래쪽으로 $N-1$번 이동하는 경로입니다. 어떤 경로를 선택하더라도 총 $N-1$번의 가로 이동과 $N-1$번의 세로 이동을 해야 합니다. 모든 도로의 길이가 1이므로, 총 주행 거리는 $(N-1)+(N-1)=2(N-1)$이 됩니다. 이 값은 항상 고정됩니다.

2. 피봇턴 최대화: 피봇턴은 가로 이동에서 세로 이동으로 바뀌거나, 세로 이동에서 가로 이동으로 바뀔 때 발생합니다. 피봇턴 횟수를 최대로 만들려면 이동하는 방향을 최대한 자주 바꿔주면 됩니다. 예를 들어, $(1,1)\to (1,2)\to (2,2)\to (2,3)\to (3,3)$과 같은 경로를 생각해봅시다.

   • $(1,1)\to (1,2)$: 가로 이동
   • $(1,2)\to (2,2)$: 세로 이동 (첫 번째 피봇턴 발생)
   • $(2,2)\to (2,3)$: 가로 이동 (두 번째 피봇턴 발생)
   • $(2,3)\to (3,3)$: 세로 이동 (세 번째 피봇턴 발생)

   총 $2(N-1)$번의 이동이 있습니다. 만약 첫 번째 이동을 제외한 모든 이동에서 이전 이동과 다른 방향으로 움직인다면, 우리는 가능한 한 많은 피봇턴을 수행할 수 있습니다. 즉, $K$번의 이동이 있다면, 방향 전환은 최대 $K-1$번 발생할 수 있습니다 (각 이동 후 방향을 바꿀 수 있는 지점). 따라서, 총 이동 횟수가 $2(N-1)$이므로, 피봇턴의 최대 횟수는 $2(N-1)-1$이 됩니다.

이 두 값을 계산하여 출력하면 됩니다.

정답 코드

def solve():
  n = int(input())
 
  distance = (n - 1) * 2
  turning = distance - 1
 
  print(distance, turning)

연관 페이지

참고 문헌 / 사이트