딩동댕 코딩유치원

문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 입력 입력의 첫째 줄에 계단의 개수가 주어진다. 둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다. 출력 첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다. 입력 예제 6 10 20 15 25 10 20 출력 예제 75 문제 풀이 각 경우에서의 최댓값을 구해야 하므로 dp[0]의 값은 array[0]..

문제 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다. 입력 예제 3 26 40 83 49 60 57 13 89 99 3 1 100 100 100 1 100 100 100 1 출력 예제 96 3..

문제 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 출력 첫째 줄에 답을 출력한다. 입력 예제 10 10 -4 3 1 5 6 -35 12 21 -1 10 2 1 -4 3 4 -4 6 5 -5 1 출력 예제 33 14 문제 풀이 연속되는 수의 합 중 가장 큰 값을 구해줘야 하므로 항상 현재 인덱스의 값 + 이전 인덱스의 값과, 현..

문제 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 입력 예제 6 10 20 10 30 20 50 출력 예제 4 문제 풀이 간단하게 앞 뒤 숫자를 비교하여 뒤에 있는 숫자가 더 큰 경우 인덱스의 값을..

문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 입력 예제 2 출력 예제 1 문제 풀이 i번째 인덱스의 값은 i를 1로 만드는 데 걸리는 횟수 이므로 맨 처음 1을 빼서 i값을 만드는 값을 i번째 인덱스에 넣는다. 그 후, 만약 i가 2나 3의 배수라면, 나누기 연산을 한 값이 최소 연산 횟수 일 것이므로, [i // 2], [i//3]번째 인덱스의 값에 1을 더해서 넣어준다. 따라서 점화식은 아래와 같다. if (i % 3 == 0 or i % 2 == 0) dp[i] = min(..

문제 [Python] 백준 1904번 01타일 성공 01타일 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 14112 5932 4958 41.399% 문제 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리 chancoding.tistory.com 입력 첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 출력 첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다. 입력 예제 4 출력 예제 5 문제 풀이 조건을 살펴보면 i번째 가능한 타일의 개수는 (i - 1)의 개수 + (i - 2)의 개수이다. 따라서 점화식은 아래와 같다. dp[i] = (dp[i -..

문제 두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다. 삽입(Insert): 특정한 위치에 하나의 문자를 삽입합니다. 삭제(Remove): 특정한 위치에 있는 하나의 문자를 삭제합니다. 교체(Replace): 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다. 이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미합니다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요. 예를 들어 "sunday"와 "saturday"의 최소 편집 거리는 3입니다. 입력 두 문자열 A와 B가 한줄에 하나씩 주어집니..

문제 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 입력 첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000) 출력 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. 입력 예제 7 3 10 5 20 1 10 1 20 2 15 4 40 2 200 10 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 출력 예제 45 55 문제 풀이 다음 상담이 가능한 날은 오늘 날짜 + 상담에 소요되는 날이다. 따라서 최대 수익은 이번 상담으로 받는 돈 + 다음 상담 가능한 날짜 ..

문제 못생긴 수란 오직 2, 3, 5 만을 소인수로 가지는 수를 의미한다. 다시 말해 오직 2, 3, 5를 약수로 가지는 합성수를 의미한다. 1은 못생긴 수라고 가정한다. 따라서 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... } 순으로 이어지게 된다. 이 때, n번째 못생긴 수를 찾는 프로그램을 작성해라. 예를 들어 11번째 못생긴 수는 10이다. 입력 첫째 줄에 n이 입력된다.(1

문제 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력한다. 입력 예시 7 15 11 4 8 5 2 4 출력 예시 2 문제 풀이 가장 긴 증가하는 부분 수열 구하는 전형적인 다이나믹 프로그래밍 문제 증가하는..