본문 바로가기

Algorithm/DP(Dynamic Programing)

 (72)
(C++) - 백준(BOJ) 1937 : 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net dp로 푼 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 상, 하, 좌, 우로 이동 및 비교를 위한 일차원 배열 dr, dc, 대나무 숲 정보를 저장할 이차원 배열 bamboo, 판다의 정보를 저장할 이차원 배열 live, 대나무 숲의 한 변 너비 n, 정답을 출력할 변수 ans를 선언해 줍니다. 📔 풀이과정 bfs혹은 dfs를 수행하려면 brute force처럼 i,j에 배치해 모든 ..
(C++) - 백준(BOJ) 20500 : Ezreal 여눈부터 가네 ㅈㅈ https://www.acmicpc.net/problem/20500 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net dp문제였습니다. 📕 풀이방법 📔 입력 및 초기화 10,000,000,007로 나눈 답을 출력해야하므로 MOD 상수를 선언해줍니다. n과 2차원 배열 d를 선언하고 n을 입력받습니다. memoization을 위해 d배열은 -1로 초기화해줍니다. 📔 풀이과정 15는 3과 5의 공배수입니다. 따라서 15의 배수는 3의 배수 특징과 5의 배수 특징을 합친 특징을 가지고 있습니다. 특징은 다음과 같습니다. 1. 각 자리의 합이 3의 배수 2. 마지막 자리가 0또는 5인 수 memoization을 이..
(C++) - 백준(BOJ) 17831 : 대기업 승범이네 https://www.acmicpc.net/problem/17831 17831번: 대기업 승범이네 첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대 www.acmicpc.net tree dp 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 사수, 부사수 관계를 인접 그래프로 나타내기 위한 변수 graph, 각 회사원의 능력을 입력할 일차원 배열 ability, 회사원의 수 n, dp함수를 수행하며 memoization을 수행할 d배열을 선언 후 입력받습니다. graph에 값을 저장할 때 i번 회사원의 사수를 입력하는 형태이므로 graph[사수..
(C++) - 백준(BOJ) 16507 : 어두운건 무서워 https://www.acmicpc.net/problem/16507 16507번: 어두운 건 무서워 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사 www.acmicpc.net 2차원 누적합 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 r(행), c(열), q(질의 개수), board(입력받을 2차원 배열), sum(누적합을 저장할 2차원 배열) 을 선언합니다.적절히 입력받습니다. 📔 풀이과정 1. 가로방향으로 구간합을 구해줍니다. 첫 번째 열에는 그냥 board의 값이 저장됩니다. 2. 세로방향으로 구간합을 구해줍니다...
(C++) - 백준(BOJ) 2098 : 외판원 순회 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 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. n, 도시로 가는 비용 cost, d배열을 선언합니다. 2. n입력 후, n행, n열만큼 i -> j도시로 가는 비용들을 cost에 입력합니다. 📔 풀이과정 n이 16인 경우 도시의 경로는 16!로 매우 많습니다. 16개의 도시를 순열로 배열하는 것과 같기 때문입니다. 도시의 상태를 빠르게(O(1)) 알..
(C++) - 백준(BOJ) 17485~6번 : 진우의 달 여행 (Small, Large) https://www.acmicpc.net/problem/17484 17484번: 진우의 달 여행 (Small) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net https://www.acmicpc.net/problem/17485 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net dp 문제였습니..
(C++) - 백준(BOJ) 1823번 : 수확, 13002번 : Happy Cow https://www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net https://www.acmicpc.net/problem/13002 13002번: Happy Cow 천나라에 살고있는 민호는 애지중지하는 소 한마리가 있다. 소의 행복은 곧 민호의 행복이기 때문에 가지고 있는 전재산을 털어 최고로 맛있는 여물 N개를 구매 했다. 민호는 여물을 관리하기 www.acmicpc.net dp 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. n, 벼의 가치를 입력받을 일차원 배열 a, 점화식을 계산할 이..
(C++) - 백준(BOJ) 3745번 : 오름세 https://www.acmicpc.net/problem/3745 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net LIS문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. vector d를 선언합니다. 2. n을 EOF가 아닌동안 입력받습니다. 3. d를 n만큼 resize 합니다. n개의 방을 저장할 수 있게 됩니다. 📔 풀이과정 n개의 수를 입력받을 때 마다 답을 저장할 vector인 d변수에 대해 d.begin부터 lis의 길이인 length까지의 범위에서 입력 받은 수를 key로 하여 lower_bo..

티스토리툴바