본문 바로가기

다이나믹프로그래밍41

백준 15486 퇴사 2 c++ (dp) 문제 출처 : https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수.. 2021. 11. 12.

백준 1053 팰린드롬 공장 c++ (dp) 문제 출처 : https://www.acmicpc.net/problem/1053 1053번: 팰린드롬 공장 팰린드롬이란, 앞에서부터 읽었을 때와, 뒤에서부터 읽었을 때가 같은 문자열이다. 모든 문자열이 팰린드롬이 아니기 때문에 다음과 같은 4가지 연산으로 보통 문자열을 팰린드롬으로 만든다. www.acmicpc.net 문제 팰린드롬이란, 앞에서부터 읽었을 때와, 뒤에서부터 읽었을 때가 같은 문자열이다. 모든 문자열이 팰린드롬이 아니기 때문에 다음과 같은 4가지 연산으로 보통 문자열을 팰린드롬으로 만든다. 문자열의 어떤 위치에 어떤 문자를 삽입 (시작과 끝도 가능) 어떤 위치에 있는 문자를 삭제 어떤 위치에 있는 문자를 교환 서로 다른 문자를 교환 1, 2, 3번 연산은 마음껏 사용할 수 있지만, 마지막 .. 2021. 11. 9.

백준 1106 호텔 c++ (dp) 문제 출처 : https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 문제 세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다. 형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다. 예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 .. 2021. 11. 9.

백준 14462 소가 길을 건너간 이유 8 c++ (dp) 문제 출처 : https://www.acmicpc.net/problem/14462 14462번: 소가 길을 건너간 이유 8 존 (우리가 지금까지 도와 주었던 존과는 다른 인물이다)의 농장에는 N 종류의 소가 있다. 각각 1번 종, 2번 종, ..., N번 종 (1 ≤ N ≤ 1000)이다. 만약 |a−b| ≤ 4라면 a번 종과 b번 종의 소는 친하지만 www.acmicpc.net 문제 존 (우리가 지금까지 도와 주었던 존과는 다른 인물이다)의 농장에는 N 종류의 소가 있다. 각각 1번 종, 2번 종, ..., N번 종 (1 ≤ N ≤ 1000)이다. 만약 |a−b| ≤ 4라면 a번 종과 b번 종의 소는 친하지만, 그렇지 않으면 사이가 나쁘다. 농장에는 일자형 길이 있고, 양쪽에 목초지가 N개씩 있다. 왼.. 2021. 11. 3.

백준 1663 XYZ 문자열 c++ (dp) 문제 출처 : https://www.acmicpc.net/problem/1663 1663번: XYZ 문자열 첫째 줄에 문제 번호가 주어진다. 이는 1, 2, 3 중 하나이다. 이어서 둘째 줄에 자연수 N(1 ≤ N ≤ 100)이 주어진다. 문제 2인 경우는 셋째 줄에 자연수 k가, 문제 3인 경우는 셋째 줄에 X 또는 Y 또는 Z www.acmicpc.net 문제 "XYZ 문자열"이란 아래와 같은 문법에 의해 단계별로 만들어지는 일련의 문자열들을 뜻한다. "XYZ 문자열"은 세 개의 문자 X, Y, Z로만 이루어진다. 1단계 "XYZ 문자열"은 X로 시작한다. 다음 단계의 "XYZ 문자열"은 바로 이전 단계의 "XYZ 문자열"에서 아래와 같은 규칙에 따라 변형되어 만들어진다. X는 YZ로 변형된다. Y는.. 2021. 10. 26.

백준 2407 조합 c++ (조합,dp,파스칼의 삼각형, 문자열) 문제 출처 : https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 문제 nCm을 출력한다. 입력 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) 출력 nCm을 출력한다. 알고리즘 분류 수학 다이나믹 프로그래밍 조합론 임의 정밀도 / 큰 수 연산 풀이 파스칼 삼각형 : https://ko.wikipedia.org/wiki/%ED%8C%8C%EC%8A%A4%EC%B9%BC%EC%9D%98_%EC%82%BC%EA%B0%81%ED%98%95 조합+dp+문자열 문제이다. 우선 nCr은 n!/r!*(n-r)!로 구할 수 있지만, 문제에선 입.. 2021. 10. 2.

백준 11057 오르막 수 c++ (dp) 문제 출처 : https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. 입력 첫째.. 2021. 10. 2.

백준 2352 반도체 설계 c++ (dp) 문제 출처 : https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 문제 반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다. 예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이.. 2021. 9. 30.

백준 9465 스티커 c++, Kotlin (dp) 문제 출처 :https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티.. 2021. 9. 30.

이전 1 2 3 4 5 다음

티스토리툴바