[백준 3101번] 토끼의 이동(파이썬)

https://www.acmicpc.net/problem/3101

3101번: 토끼의 이동

이 문제를 보고

'지그재그로 가는 모든 경로를 다 구하자'

라는 마인드를 가지면 바로 시간초과.

N이 10만까지 된다면

지그재그 하다가 시간이 다 소요가 됩니다.

 

결국 해당 좌표지점의 수를 예측해서 더하는 게 관건.

이 부분이 상당히 까다로웠습니다.

수학적 능력이 필요한 부분이라...

생각하기 상당히 어렵습니다.

 

제 나름대로 스스로 풀어볼려다가

구글링으로 힌트를 얻은 뒤에

제 방식대로 구성했습니다.

#백준 3101번 토끼이동

N,K=map(int,input().split())
command=list(input().rstrip())
sx,sy=0,0
answer=1

f_number=[0]*(2*N)
f_number[0]=1

for i in range(1,N*2):
    if i<=N:
        f_number[i]=f_number[i-1]+(i)
    else:
        f_number[i]=f_number[i-1]+(N-i)%N

for c in command:
    if c=='U':
        sx-=1
    elif c=='D':
        sx+=1
    elif c=='L':
        sy-=1
    elif c=='R':
        sy+=1

    line_num=sx+sy
    start=f_number[line_num]

    if line_num<N:
        if line_num%2==0:
            num=start+sy
        else:
            num=start+sx

    else:
        if line_num%2==0:
            num=start+N-sx-1
        else:
            num=start+N-sy-1

    answer+=num

print(answer)

https://dailymapins.tistory.com/138

[백준/3101/파이썬] 토끼의 이동

참고를 했던 페이지입니다.

 

수학적으로 좌표를 어떻게 표현해야할지

생각할 수 있는 좋은 문제입니다.