林's

이 문제는 삼성 역량 테스트 기출문제입니다. 당시 기억으로는 버스가 이동할 수 있는 경로의 가짓수를 구하라는 문제였는데. 놀랍게도 하루만에 복기돼서 버스가 파이프로 바뀌었던걸로 기억하고 있습니다. ㅋㅋ 그 때는 버스의 시작모양이 세로일 수도 있고 대각선일 수도 있었던 것 같은데. 이번 문제는 반드시 파이프(=버스)가 가로로 시작하네요~ 여담이지만, 최근 이 문제의 제한시간을 0.5초로 줄였더군요! 그래서 더욱이 DP가 아니면 풀 수 없는 문제가 되고 말았습니다. 파이프1번 문제의 경우에는 BFS로 풀다 시간초과로 털리는 쓴맛을 보았기에,, 이해도 된 겸 포스팅으로 DP적 접근에 관한 아이디어를 나눠보겠습니다. 1). 점화식이란 무엇일까? DP는 흔히, 점화식을 세운다라고 표현하곤 합니다. ...더보기 (..