BOJ 1405 - 미친 로봇

Joonas' Note

BOJ 1405 - 미친 로봇 본문

알고리즘/문제 풀이

BOJ 1405 - 미친 로봇

2019. 3. 14. 15:36 joonas 읽는데 1분
  • 문제
  • 코드

링크: https://www.acmicpc.net/problem/1405

문제

동서남북 각 방향으로 이동할 확률이 주어지고, 로봇이 동선을 겹치지 않게 n번 움직일 확률을 구하는 문제이다.

(0, 0)부터 출발한다고 생각하면 동서남북 경계의 끝은 (14, 0), (-14, 0), (0, 14), (0, -14) 일텐데 음수를 없애기위해 출발점을 (15, 15)로 설정하면 편하다.

좌표값을 들고 다니는 이유는 동선이 겹쳐서는 안되기 때문에, 다시 말해 이미 방문한 위치는 다시 방문하지 않도록 하기 위해서이다.

어떤 한 위치에서 생각했을 때, 동쪽으로 이동한다면 동쪽에서 나오는 모든 확률은 (그 위치에서 발생하는 확률 * 동쪽으로 이동할 확률)이 된다. 이걸 동서남북 모든 방향과 모든 위치마다 반복한다면 정답을 구할 수 있다.

코드


'알고리즘 > 문제 풀이' 카테고리의 다른 글

BOJ 9375 - 패션왕 신해빈  (0) 2019.03.21
프로그래머스 - 나머지 한 점  (0) 2019.03.16
BOJ 2096 - 내려가기  (0) 2019.03.13
BOJ 16964 - DFS 스페셜 저지  (0) 2019.03.12
BOJ 11447 - Colby’s Costly Collectibles  (0) 2019.03.11
Comments