문제 해석

아래 그림의 왼쪽 상단에서 오른쪽 하단까지 이동하는 경로를 출력하는 문제인데 다음과 같은 제약 조건이 있음

1) 항상 오른쪽 또는 아래쪽으로만 이동 가능

2) 앞서 출발한 리디아가 지나간 경로를 회피해야 함. 예를 들어서 리디아가 (i,j)에서 (i+1, j)를 지나갔다면 나는 (i,j)와 (i+1, j)를 모두 지나갈 수 없음. 다만 (i,j)나 (i+1, j)만 밟고 지나가는 것은 허용됨. 즉, 나의 경로가 리디아의 경로와 여러 점에서 교차하는 것은 허용되나 교차점이 2개 이상 이어지면 안됨.

위 그림에서처럼 리디아의 경로와 나의 경로는 여러 곳에서 교차하지만 2회 이상 연속되지는 않으므로 유효함 

입력

리디아의 경로가 S(아래쪽) E(오른쪽) 의 순열로 주어지고 최대 길이는 50000.

풀이

행렬을 전치(transpose)시키는 문제. 주어진 리디아의 경로에서 S->E, E->S 로 바꾸면 유효한 경로가 됨.

show >>

 

'Dev' 카테고리의 다른 글

[google codejam 2019 QR] Cryptopangrams  (0) 2019.04.17
[google codejam 2019 QR] P1 Foregone Solution  (0) 2019.04.11
PingBot Architecture  (0) 2014.05.04
Posted by yeori
,