백준2 백준 - 13305 주유소 이번 문제는 주유소 문제로 각 도시마다 기름 값이 다른 주유소가 존재하고 우리는 모든 도시를 이동하기 위한 최소 비용을 구해야 한다. 다른건 제쳐두고 기본적인 것만 생각해보면 결국 1. 당장 다른 도시로 가기 위해서는 기름이 필요 2. 도시를 거치며 더 싼 주유소가 나오기 전 까지는 가장 저렴한 주유소에서 왕창 주유하고 가면 된다. 이러한 로직은 결국 도시를 하나씩 거치면서 이제까지 만난 기름의 최소값 만을 저장하며 순차적으로 총 가격에 더해주면 된다. 이러한 풀이는 그리디 알고리즘으로 현재까지 만난 주유소 중 기름 값이 가장 싼 주유소에서 주유하면 전체 주유 비용의 최소 값을 구할 수 있다는 개념이다. 풀이 def run(): N = int(input()) length_lst = list(map(int.. 2021. 9. 15. 백준 - 16928 뱀과 사다리 게임 이번 문제는 '뱀과 사다리 게임'이라는 문제인데 해당 게임은 어렸을 때 몇 번 해본 기억이 난다. 아래에서 맨 꼭대기로 올라가는 문제인데 중간 중간 사다리나 뱀을 타고 올라가기도 내려가기도 했던 게임 여기서 우리는 1~6의 값을 가진 주사위를 최소 몇 번 던져서 도착 지점에 갈 수 있는지 구해야 한다. 그리고 어떤 발판은 사다리로 더 멀리 있는 지점에 도달할 수 있고 어떤 발판은 뱀으로 다시 내려오기도 한다. 어떠한 경로를 최소 단계로 도달한다? -> BFS일 것이라고 생각했다. DFS의 경우에는 불가능한 수로 너무 깊게 빠질 수 있으므로 최소 단계를 구하는 데는 적합하지 않다. + 깊이에 따라 스택 오버플로가 발생할 수도 있고 또한 단순히 위 게임의 그림을 보고 발판을 10 X 10의 2차원 배열로 선.. 2021. 9. 15. 이전 1 다음 반응형
