🎨 문제 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 📘 풀이 이 문제는 DP로 풀 수 있습니다. 문제를 정리하면 다음과 같습니다. 길이가 최대 2,000인 수열이 주어진다. 수열의 [S, E] 구간의 수가 펠린드롬인지 판별한다. 판별 질의는 최대 1,000,000 주어진다. 주어진 구간이 펠린드롬인지 판별하는 일반적인 방법은 구간 양 끝점부터 서로 같은 수인지 비교를 하는 방법입니다. 이 경우 한 쿼리 당 최대 수열의 길이만큼의 확인이 필요합니다. 하지만 질의가 1,000,000번 주어지기 때문에 매 번 비교를 할 수 없습니다. 그래서 이전 쿼..
🎨 문제 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을 빼주어도 됩니다. 발의 위치는 다섯가지로 중앙, 위, 아래, 왼쪽,..
