다이나믹 프로그래밍
[BOJ] 20152 - Game Addiction
문제 출처 백준 20152 - Game Addiction 풀이 어떤 칸 x에 도달하는 최단 경로를 저장해주는 배열(map)과 x에 최단 경로로 도착할 수 있는 모든 경로들의 갯수를 저장해주는 배열(acc)을 따로 선언해주어야 합니다. - 큐에 데이터를 넣지 않는 경우 1. x에 도달했을 때 최단 경로가 아닐 경우 2. x가 이미 최단 경로가 갱신되어 있는 경우 즉, x에 최단 경로로 최초로 도달했을 때 방문 표시를 해주고 이후에 최단 경로로 도달하는 경로들은 x위치에 경로의 갯수만 저장해주는 것입니다. 위와 같이 진행했을 때 목적지에 최단 경로로 도달할 수 있는 모든 경우의 수를 구할 수 있습니다. 그 이유는 다음과 같습니다. 큐는 선입선출(FIFO) 자료구조 입니다. 먼저 들어온 데이터가 먼저 나가는 ..
[BOJ] 2502 - 떡 먹는 호랑이
문제출처 백준 2502 - 떡 먹는 호랑이 풀이 주어진 날이 x라면 x-1날은 주어진 날 전날을 말합니다. x(떡의 갯수) - x-1(떡의 갯수) = x-2(떡의 갯수) 즉, 주어진 D째 날에서 전날의 떡의 갯수를 빼주는 방식으로 전전날의 떡의 갯수를 구했습니다. x-1(떡의 갯수)를 구하기 위해서 현재 날짜의 떡의 갯수보다 작은 경우를 모두 가정하여 빼주었습니다. 예를 들어 7번째 날의 떡의 갯수가 7개라면 6~1까지 떡의 갯수를 빼주었습니다. 주어진 D째 날의 떡의 갯수에서 전날의 떡을 빼주는 과정을 D만큼 반복하여 첫째 날까지 나누어 줄 수 있는지 직접 돌려 보았다. 코드 small-j/BOJ_Algorithm Contribute to small-j/BOJ_Algorithm development b..