[백준 11727] 2×n 타일링 2
풀이 해설 n이 1일 때, 2x1타일 하나가 들어갈 수 있고, n이 2일 때 (1x2, 1x2), (2x1, 2x1), (2x2) 3가지 경우의 수로 타일을 채울 수 있다. 그리고 n이 3일 때를 보면, 2x1타일을 왼쪽이 위치시켰을 경우 n이 2일 때 경우의 수만큼 채우고, n이 1일 때 경우의 수인 2x1타일이 2번 채워지는 것을 볼 수 있다. n이 4일 경우에도 마찬가지이다. 이것을 이용해 점화식을 짜본다면, n = n-1 + (n-2) * 2가 나온다. 시간복잡도 N만큼 순회하므로, O(N)이다. 코드 package _2xn타일링2_11727; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamR..
[백준 16202] MST 게임
문제 16202번: MST 게임 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 풀이 문제 이름에도 나와 있듯 MST(최소 신장 트리)를 사용하는 문제이다. 문제에서 제시한 MST의 조건은, 스패닝 트리를 구성하는 간선의 개수는 N-1개이다. 그래프의 임의의 두 정점을 골랐을 때, 스패닝 트리에 속하는 간선만 이용해서 두 정점을 연결하는 경로를 구성할 수 있어야 한다. 이다. 주어진 그래프에서 MST 값을 구하는 문제인데, 주의할 점은 턴마다 최소..
[백준 14002] 가장 긴 증가하는 부분 수열4
문제 14002번: 가장 긴 증가하는 부분 수열 4 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 이 문제는 수열이 주어질 때 가장 긴 증가하는 부분수열의 길이와 요소들을 순차적으로 출력하는 문제이다. LIS와 Stack의 개념을 적용해 풀이해보자. LIS(Longest Increasing Subsequence) LIS의 약어를 해석해보면 최장 증가 부분 수열이다. 이것은 문제가 요구하는 수열을 의미하는 용어임을 알 수 있..
