Joonas' Note

Joonas' Note

BOJ 1405 - 미친 로봇 본문

알고리즘/문제 풀이

BOJ 1405 - 미친 로봇

2019. 3. 14. 15:36 joonas

    링크: 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