DP13 [백준] 돌다리 건너기 https://www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 1. 문제이해 마법의 두루마리에 적혀있는 단어의 문자순서대로 악마의 돌다리와 천사의 돌다리를 번갈아가면서 밟을 수 있는 모든 경우의 수를 구하는 문제입니다. 2. 문제접근 접근 방식: DP 제일 못하는 재귀 DP입니다. DP[k][i][j]라고 정의했을때 k = 0인 경우는 천사의 돌다리를 건널 차례일 때 마법의 두루마리의 i번째 문자를 돌다리에서 j인덱스부터 찾는 경우를 의미합니다. 재귀를 돌면서 돌다리를.. 2023. 5. 11. [백준] 등산 마니아 https://www.acmicpc.net/problem/20188 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net import sys, math from collections import deque, defaultdict sys.setrecursionlimit(10 ** 8) #sys.stdin = open("input.txt", "r") input = sys.stdin.readline n = int(input()) dp = [0] * (n + 1) graph = defaultdict(list) for .. 2023. 4. 30. [백준] 비즈 공예 https://www.acmicpc.net/problem/1301 1301번: 비즈 공예 첫째 줄에 다솜이가 가지고 있는 구슬의 종류 N이 주어진다. N은 3보다 크거나 같고, 5보다 작거나 같다. 둘째 줄부터 N개의 줄에 각각의 구슬이 총 몇 개 있는 지주어진다. 첫째 줄에는 1번 구슬, www.acmicpc.net import sys #sys.stdin = open("input.txt", "r") input = sys.stdin.readline n = int(input()) marble = [0] * 6 for i in range(n): marble[i] = int(input()) dp = [ [[[[[[-1 for _ in range(6)] for __ in range(6)] for ___ in r.. 2023. 4. 24. [백준] 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. 문제 이해 제일 왼쪽 위 칸에서부터 제일 오른쪽 아래 칸으로 이동할 때 계속해서 높이가 낮아지도록 이동할 수 있는 내리막길로만 이동하는 경로의 개수를 구하는 문제입니다. 2. 문제 접근 첫번째 접근: DFS 단순하게 왼쪽 위 칸에서부터 오른쪽 아래 칸으로 이동을 DFS로 풀이하면 시간초과가 날 것이라고 생각했습니다. 그래서내리막 경로에 해당하는 칸들에 방문처리를 하고 만약에 탐색 도중 방문 처리된.. 2023. 4. 21. [백준] 수확 https://www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 1. 문제 이해 1XN의 긴 밭의에 벼가 있고 양쪽 끝에서만 벼를 수확할 수 있습니다. 벼를 수확할 때 얻을 수 있는 이익은 K일에 수확할 경우 (벼의 가치 * K)를 얻을 수 있게 됩니다. 따라서, 양끝에서 벼를 어떤 순서로 수확하느냐에 따라 얻을 수 있는 이익이 달라지게 되는데 이중 얻을 수 있는 최대 이익을 계산해야합니다. 2. 문제 접근 첫번째 접근: 그리디 양쪽 끝에서만 벼를 수확할 수 있으므로 deque를 생각했습니다. .. 2023. 4. 17. [백준] 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net DP를 활용하여 풀이하였습니다. 대나무의 수가 증가하는 방향으로 움직어야합니다. 반대로, 대나무의 수가 감소하는 방향으로 움직여도 됩니다. 저는 대나무의 수를 큰 수로 내림차순으로 정렬을 하고 현재 대나무의 위치에서 사방탐색을 진행해주면 DP 배열을 채워주면 됩니다. 만약, 현재 대나무의 수보다 작은 대나무 숲이 인접해있다면 현재 대나무 숲에서 이동이 가능합니다. 따라서, 현재까지 이동.. 2023. 4. 15. [백준] 동전 분배 https://www.acmicpc.net/problem/1943 1943번: 동전 분배 세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1 ≤ N ≤ 100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원 www.acmicpc.net 정말 이 문제가 어떻게 골드3 문제인지 이해가 안되는 문제였습니다. 처음에는 그리디로 접근을 했습니다. 모든 동전의 개수를 짝수로 맞춰주면 된다고 생각을 했고 동전의 가격을 내림차순으로 정렬하여 가격이 큰 동전의 개수를 짝수개로 먼저 맞춰주면서 내려오는 풀이법을 생각했는데 가격의 큰 동전의 가격에 맞게 조합을 짤 경우의 수가 너무 많다고 하여 포기하였습니다. 그래서 알고리즘 분류를 .. 2023. 4. 12. [백준] 외판원 순회 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 비트마스킹과 DP를 같이 활용해야하는 문제입니다. 먼저, dp[i][j]의 정의는 다음과 같습니다. 현재 i의 조합을 방문하고 현재 j에 왔을 때, 순회를 마치기 위해 필요한 최소 비용이 됩니다. 이 문제의 핵심은 순회를 하기 때문에 어디서 시작을 해도 무방합니다. 저의 경우에는 0번 노드를 시작점으로 두었으므로 visited는 1로 시작을 하게 됩니다. dp.. 2023. 4. 6. [백준] 게임 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net DFS + 메모이제이션을 활용하여 해결하였습니다. DFS로 탐색해나가면서 현재 위치부터 움직일 수 있는 최대 횟수를 저장하고 있고 탐색 도중 메모이제이션되어 있는 부분을 만나면 탐색을 진행하지 않고 적혀있는 값을 활용하면 됩니다. 싸이클을 탐색하는 방법은 현재 DFS로 탐색중인 경로를 visited배열로 저장하고 있다가 다음 지점이 visited가 true이면 싸이클이 발생한 경우임을 알 수 있습.. 2023. 4. 6. 이전 1 2 다음
