링크
돌던지기
난이도
- 플레4
- 엄청 어려운건 아니지만, 짜증나는 입력과 출력을 빠르게 안하면 무조건 시간초과인 그지같은 문제이다.
문제요약
- 하나의 판에 맨위의 행의 열에서 돌을 던지고 아래 행으로 떨어진다.
- X는 벽으로 만나면 멈추고 위에 O로 돌이 쌓인다.
- O는 돌로 만나면 미끌어진다.
- 왼쪽, 왼쪽아래가
.빈칸이면 왼쪽으로
- 오른쪽, 오른쪽아래가
.빈칸이면 오른쪽으로
- 못미끌어지면 멈추고 위에 O로 돌이 쌓인다.
접근
- 기본 시뮬레이션
- 30000의 행을 가지고 있고, 입력되는 N도 크기 때문에 오래걸려 시간초과가 발생
- 이를 해결하기 위해서는 해당 열이 어디에 도착할지 바로 알수 있는 메모이제이션이 필요
- memo를 추가(memo[열] = [도착행,도착열]의 형태로 2차원 배열)
- 2차원 배열로 특정 열이 어느 위치에 마지막으로 갔는지 저장을 한다.
- 하지만 다른 열이 그자리에 돌을 놓았을때 그 전위치가 어딘지 알아야 하지만, 단순히 바로위 행인지, 오른쪽에서 미끌어져서 왔는지 등이 파악이 안된다.
- memo를 개선(memo[열] = [1번째 행,1번째 열],[2번째 행,2번째 열]로 지나온 모든 경로를 저장)
- 마지막 원소만 보면 마지막으로 위치한 경로를 알수 있으므로 stack이 용이하다.
간단 알고리즘
- 기본 시뮬레이션에서 memo를 넣어준다.
- memo는 stack의 배열형태로 memo[열]은 해당 열을 통해 내려가면서 r,c들을 저장하는 stack을 선언해준다.
- 시작 열 startC를 받는다.
- memo[startC]로 해당하는 스택의 길이가 있는지
- stack에 값이 있을때
- 맨뒤의 stack값을 pop해주고, 출발하는 curR, curC로 지정해준다.
- stack에 값이 없으면
- 처음 진행하는 열인 경우
- curR = 0, curC=startC로 시작한다.
- 쭉 아래로 알고리즘에 맞게 이동시킨다.
- 유의할점
- 출력이 많기 때문에 그냥 system.out.println이 아니라 buffer또는 stringbuilder를 사용해야 시간초과가 안난다.
후기
- 출력만 신경쓰자… 1000줄정도 넘을거 같다 싶으면 buffered를 써서 출력하자.