🎨 문제 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 📘 풀이 이 문제는 DP로 풀 수 있습니다. 문제를 정리하면 다음과 같습니다. 길이가 최대 2,000인 수열이 주어진다. 수열의 [S, E] 구간의 수가 펠린드롬인지 판별한다. 판별 질의는 최대 1,000,000 주어진다. 주어진 구간이 펠린드롬인지 판별하는 일반적인 방법은 구간 양 끝점부터 서로 같은 수인지 비교를 하는 방법입니다. 이 경우 한 쿼리 당 최대 수열의 길이만큼의 확인이 필요합니다. 하지만 질의가 1,000,000번 주어지기 때문에 매 번 비교를 할 수 없습니다. 그래서 이전 쿼..
🎨 문제 1513번: 경로 찾기 첫째 줄에 0개 방문했을 때, 1개 방문했을 때, ..., C개 방문했을 때 총 경로의 개수를 한 줄에 공백을 사이에 두고 출력한다. 경로의 개수는 1,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 📘 풀이 이 문제는 DP로 풀 수 있습니다. 만약 완전 탐색을 할 경우 거쳐가는 오락실의 개수의 경우의 수(0~50)만큼 학원을 가는 경우의 수를 완전탐색으로 구하게 됩니다. 1,000,0007로 나누는 것을 보면 경우의 수가 아주 커서 이 방법은 옳지 않음을 짐작할 수 있습니다. 따라서 이동 경로를 기억하여 다음 연산에 사용하도록 합시다. DP문제 풀이의 중요한 포인트는 점화식도 있지만, 상태값도 중요합니다. 점화식은 특정 상태에서의 최적값을 구하는 식..
🎨 문제 https://www.acmicpc.net/problem/4781 4781번: 사탕 가게 각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다. (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00) m은 항상 소수점 둘째자리까지 주어진다. 다음 n개 www.acmicpc.net 📘 풀이 이 문제는 DP로 풀 수 있습니다. 특히 배낭 문제를 아신다면 쉽게 풀 수 있습니다. 문제의 특이한 점은 사탕의 가격이 소수점 둘째자리까지 표현된 소수인 점입니다. 소수 간 연산은 오차가 발생할 수 있으므로 소수를 정수로 변환해 주었습니다. 저는 문자열에서 '.'을 지워주는 방식을 선택했습니다. String input = "8.00"; String..
🎨 문제 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 📘 풀이 배낭 문제와 유사한 문제입니다. 배낭 문제는 DP 배열을 다음과 같이 사용한다면 행: 넣을 수 있는 무게 열: 물건의 종류 저장: 물건의 최대 가치 이 문제는 다음과 같이 생각할 수 있습니다. 행: 사용할 수 있는 비용 열: 앱의 종류 저장: 앱의 최대 메모리 DP의 시간 복잡도는 앱의 종류(N), 사용할 수 있는 최대 비용(MAX_COST)에 의해 N x MAX_COST가 됩니다. N의 최대값은 100, 최대 비용은 단일 앱의 최대 비용(100) x..
🎨 문제 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 📘 풀이 DP와 분할정복을 혼합하여 풀었습니다. 완전 탐색의 경우 왼발과 오른발을 쓰는 지(두가지)와 입력 수열의 길이가 100,000이 최대이므로 시간 복잡도가 2의 100,000제곱으로 TLE가 발생합니다. DP 배열 DP = int[눌러야하는 발판][왼발 위치][오른발 위치] 눌러야할 발판은 입력받은 배열의 길이입니다. 마지막 발판은 0이므로 1을 빼주어도 됩니다. 발의 위치는 다섯가지로 중앙, 위, 아래, 왼쪽,..
