[문제링크]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 문제..

[문제 링크]https://www.acmicpc.net/problem/11053문제 설명수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50} 이고, 길이는 4이다. 입력첫째 줄에 수열 A의 크기둘째 줄에 수열 A를 이루고 있는 원소들출력가장 긴 증가하는 부분 수열의 길이입출력 예시입력예시출력예시610 20 10 30 20 504 문제 풀이다이나믹 프로그래밍으로 풀이dp[i] : array[i]를 마지막 값으로 가지는 증가 부분 수열들 중에서 가장 긴 부분수열의 길이array[i]가 어떠한 증가 부분 수열의 마지막 값이 되려면, ar..

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

[문제 링크]https://www.acmicpc.net/problem/2579문제 설명계단 오르기 게임은 계단 아래 시점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다.과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다.1. 계단은 한 번에 한 계단 or 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면 이어서 다음계단이나, 다음다음계단을 밟은 수 있다.2. 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 포함되지 않음3...

문제 설명못생긴 수란 오직 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의 배수를 구하면 다음과 같다.못생긴 수 배수한 값..