본문 바로가기

다이나믹 프로그래밍90

[백준] 17090번 : 미로 탈출하기 (C++) 17090번 : 미로 탈출하기 문제) 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문자가 U인 경우에는 (r-1, c)로 이동해야 한다. R인 경우에는 (r, c+1)로 이동해야 한다. D인 경우에는 (r+1, c)로 이동해야 한다. L인 경우에는 (r, c-1)로 이동해야 한다. 미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한 칸이란, 그 칸에서 이동을 시작해서 칸에 적힌대로 이동했을 때, 미로의 경계 밖으로 이동하게 되는 칸을 의미한다. 입력 : 첫째 줄에 미로의 크기 N, M(3 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개의 .. 2023. 8. 18.
[백준] 17484번 : 진우의 달 여행 (Small) (C++) 17484번 : 진우의 달 여행 (Small) 문제) 우주비행이 꿈이였던 진우는 음식점 '매일매일싱싱'에서 열심히 일한 결과 달 여행에 필요한 자금을 모두 마련하였다! 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다. 진우는 여행경비를 아끼기 위해 조금 특이한 우주선을 선택하였다. 진우가 선택한 우주선의 특징은 아래와 같다. 1. 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다. 2. 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다. 진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 것이다. 최대한 돈을 아끼고 살아서 .. 2023. 8. 11.
[백준] 2600번 : 구슬게임 (C++) 10984번: 내 학점을 구해줘 문제) n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 : 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 : 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 풀이) 메모리 초과 답 ) 정답 x, 로직은 맞음. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 .. 2023. 8. 9.
[백준] 2600번 : 구슬게임 (C++) 2600번 : 구슬게임 문제) 두 사람 A와 B가 번갈아 가면서 두 개의 구슬 통에서 몇 개씩의 구슬을 꺼내는 게임을 한다. 한번에 한 사람이 한 통에서 꺼낼 수 있는 구슬의 개수는 세 가지 뿐이다. 그리고 구슬을 꺼낼 경우 두 개의 구슬 통 중에서 하나를 마음대로 선택해서 그 안에서만 꺼낼 수 있다. 즉 두 개의 통 모두에서 동시에 몇 개씩 꺼낼 수는 없다. 게임은 항상 A가 먼저하고 그 다음 B, 그 다음 A 순으로 번갈아가면서 진행된다. 그리고 자신의 차례가 되었을 때에 정해진 규칙대로 구슬을 꺼낼 수 없는 사람이 게임에서 지게 되고, 상대방은 승리하게 된다. 예를 들어 한번에 꺼낼 수 있는 구슬의 개수를 1개, 3개, 또는 4개라고 하자. 만일 두 개의 구슬 통에 각각 4개, 1개의 구슬이 있다고.. 2023. 8. 8.

티스토리툴바