[문제링크]https://www.acmicpc.net/problem/14501문제 설명상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서 남은 N일동안 최대한 많은 상담을 하려고 한다.하루에 하나씩 서로 다른 사람의 상담이 잡혀있고, 각각의 상담은 상담을 완료하는 데 걸리는 시간 T_i, 상담을 했을 때 받을 수 있는 금액 P_i로 이루어져 있다.하나의 상담을 하는데 필요한 기간이 1일보다 클 수 있기 때문에 모든 상담을 수행할 수 없다.예를 들어 N=7인 경우 상담 일정표가 다음과 같을 때, 1일의 상담을 수행하면 2일, 3일의 상담은 수행할 수 없다.N+1일 이후부터는 회사에 없기 때문에 6일, 7일의 상담은 수행할 수 없다.퇴사 전 할 수 있는 상담의..

[문제링크]https://www.acmicpc.net/problem/14888문제 설명N개의 수로 이루어진 수열과 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다.연산자는 덧셈, 뺄셈, 곱셈, 나눗셈 순서 수와 수 사이에 연산자를 하나씩 넣어서 수식을 만들 때, 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.이 때, 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행하고 나눗셈은 정수 나눗셈으로 몫만 취한다.음수를 양수로 나눌 때에는 음수를 양수로 바뀐 뒤 몫을 취하고, 그 몫을 음수로 바꾼다. 입력조건첫째 줄에 수의 개수 N둘째 줄에 수열셋째 줄에 각 연산자의 개수출력조건식 결과의 최대값과 최솟값입출력 예시입력예시출력예시25 60 0 1 0303033 4 51 0..

[문제 링크]https://www.acmicpc.net/problem/18353문제 설명N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있고, 병사를 배치할 때는전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다.배치 과정에서는 특정 위치에 있는 병사를 열외시키는 방법을 이용하고, 남아있는 병사의 수가 최대가 되도록 하고자 한다.병사에 대한 정보가 주어졌을 때, 병사의 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수를 출력하는 프로그램을 작성하시오. 입력조건첫째 줄에 병사의 수 N둘째 줄에 각 병사의 전투력출력조건남아있는 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수 입출력 예시입력예시출력예시715 11 4 8 5 2 42 문제..

문제 설명두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B를 만들고자 한다.문자열 A를 편집하여 문자열 B로 만들기 위해 사용하는 연산의 수를 '편집 거리'라고 할 때, 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요.문자열을 편집할 때는 다음의 세 연산 중 한 번에 하나씩 선택하여 편집한다.1. 삽입(insert) : 특정한 위치에 하나의 문자를 삽입합 니다.2. 삭제(remove) : 특정한 위치에 있는 하나의 문자를 삭제합니다.3. 교체(replace) : 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다. 입력조건문자열 A, B출력조건문자열 A, B간의 최소 편집 거리입출력 예시입력예시출력예시catcut1sundaysaturday3 ..

문제 설명못생긴 수란 오직 2, 3, 5만을 소인수로 가지는 수를 의미한다.(즉, 오직 2, 3, 5를 약수로 가지는 합성수)1은 못생긴 수라고 가정하고, 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...} 순으로 이어지게 된다. 이 때, n번째 못생긴 수를 찾느 ㄴ프로그램을 작성하세요. 입력조건첫째 줄에 n출력조건n번째 못생긴 수 출력입출력 예시입력예시출력예시101244 문제 풀이다이나믹 프로그래밍 풀이못생긴 수에 각각 2의 배수, 3의 배수, 5의 배수를 곱한 값도 못생긴 수가 된다.예를 들면, 문제에서 1, 2, 3, 5 는 못생긴 수 임을 알 수 있다. 이 때 각 못생긴 수에 2의 배수, 3의 배수, 5의 배수를 구하면 다음과 같다.못생긴 수 배수한 값..

다이나믹 프로그래밍이란? 큰 문제를 작은 문제로 쪼개고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.다이나믹 프로그래밍을 구현하는 방법에는 작은 문제를 재귀적으로 호출하는 방식인 Top-Down(하향식)작은 문제부터 하나씩 해결해나가면서 답을 도출하는 방식인 Bottom-Up(상향식)예제 1) 1로 만들기정수 X가 주어지고 다음 연산을 적절히 사용해서 1을 만드려고 할 때, 연산을 사용하는 횟수의 최솟값을 출력하시오.- X가 5로 나누어 떨어지면, 5로 나눈다. - X가 3로 나누어 떨어지면, 3로 나눈다. - X가 2로 나누어 떨어지면, 2로 나눈다. - X에서 1을 뺀다. 문제 해설Bottom-Up 방식 사용문제의 규칙을 찾아보면 다음과 같다.f(1) = 0f(2) =..