BOJ G4 14002 가장 긴 증가하는 부분수열4 JAVA
14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 읽기 일단 해당 문제는 흔히 LIS라고 하는 가장 긴 증가하는 부분 수열을 찾는 문제이다. 처음에 봤을 때는 tree모양이 생각났지만, 그려보니 아닌 것 같았다. 찾다 보니 DP라는 것을 알았다. 문제 풀기 N이 최대 1000이기 때문에 이중 for문을 통해 탐색해도 복잡도에 걸리지 않는 시간이다. 다음과 같은 과정을 통해 문제를 해결할 수 있다. 주어진 숫자 배열을 입력 받는..
2024. 3. 15.
BOJ G3 2482 색상환 JAVA
2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 읽기 아 역시 DP 문제는 쉽지 않다. 사실 그렇게 어려운 문제인 것 같지는 않지만.. 처음에 DFS로 했다가 2^1000이니까 당연히 시간초과가 나고, 거의 바로 아 DP인 것 같다는 생각을 했다. 그런데 처음에 N, K로 접근하지 않고, 첫 번째 원소를 선택하는 경우, 첫 번째 원소를 선택하지 않는 두 가지 경우를 생각했다. 즉, N, 2로 접근했다. 그런데 이렇게 하니 DP 배열에 경우의 수를 저장하는 게 아닌, 선택한 원소의 개수를 저장하게 되고 답을 제대로 구하지 못했다..
2024. 3. 12.
