'✍️ 코테 준비/Dynamic Programming' 카테고리의 글 목록

[동적 계획법 1] [C++] 2565번. 전깃줄

2021.02.01

www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 입력 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. 출력 첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 ..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 11054번. 가장 긴 바이토닉 부분 수열

2021.02.01

www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 입력 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다. 해결 방법 이전 문제인 가장 긴 증가하는 부분 수열의 변형 문제이다. (아직 풀지 않았다면 아래 문제를 먼저 풀어보도록 하자.) www.acmicpc.net/problem/11053 11..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 11053번. 가장 긴 증가하는 부분 수열

2021.01.25

www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 해결 방법 a[i]를 입력된 수열, dp[i]를 i번째까지 가장 긴 증가하는 부분 수열의 길이라고 ..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 2156번. 포도주 시식

2021.01.25

www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 입력 첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다. 출력 첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다. 해결 방법 포도주를 마실 수 있는 방법은 어떻게 될까? dp를 n번째 잔까지 마실 때 가장 많은 양의 포도주, grape를 n번째 잔의 포도..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 10844번. 쉬운 계단 수

2021.01.24

www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 해결 방법 우선 규칙을 찾을 필요가 있다. 길이가 1인 계단의 수는 몇 개가 있을까? 1 2 3 4 5 6 7 8 9 답은 9개 그럼 길이가 2인 계단의 수는? 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98 답은 17개 규칙이 보이는가? 보이지 않아도 된다. (본인도 푸는데 오래걸렸으니... 이 문제 많이 어려웠..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 1463번. 1로 만들기

2021.01.19

www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 입력 첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 해결 방법 우선 규칙을 찾아보자. 계산식의 경우 여러가지 경우의 수가 나올 수도 있다. N 연산 횟수 계산식 1 1 1 2 1 2/2=1 3 1 3/3=1 4 2 (4-1)/3=1 5 3 (5-1)/2/2=1 6 2 6/3/2=1 7 3 (7-1)/3/2=1 8 3 8/2/2/2=1 9 2 9/3/3=1 10 3 (10-1)/3/3=1 어떤 규칙을 찾을 수 있을까? 우선 수가 1씩 커질 ..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 2579번. 계단 오르기

2021.01.14

www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 입력 입력의 첫째 줄에 계단의 개수가 주어진다. 둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다. 출력 첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다. 해결 방법 dp 문제이므로 점화식을 찾아야한다. 도착지점에 갈 수 있는 방법은 어떻게 될까? 두 ..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 1932번. 정수 삼각형

2021.01.13

www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 입력 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 출력 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다. 해결 방법 이전 문제였던 RGB 거리 문제와 유사하다. dp를 이용할 것이므로 점화식, 즉 규칙을 찾아내야 한다. 첫번째 행은 무조건 자기 자신을 택하므로 제외 두번째 행부터는 i) 가장 좌측 원소의 경우 이전 행의 가장 좌측 원소 ii) 가장 우측 원소의 경우 이전 행의 가장 우측 원소를 무..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 1149번. RGB 거리

2021.01.13

www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다. 해결 방법 이 문제의 시간 제한은 0.5초로 짧다. 중첩 반복문을 이용한 브루트 포스의 방법..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 9461번. 파도반 수열

2021.01.13

www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100) 출력 각 테스트 케이스마다 P(N)을 출력한다. 해결 방법 처음 들어보는 새로운 수열이지만 그 규칙은 피보나치와 비슷하다. 피보나치의 점화식이 f(n) = f(n-1) + f(n-2) 였다면 N 1 2 3 4 5 6 7 8 9 P(N) 1 1 1 2 2 3 4 5 7 파도반의 점..

티스토리툴바