[C++] 백준 1309번 : 동물원 (S1)
#문제 www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net #풀이 & 학습한 내용 x가 빈공간, o가 사자가 있는공간이라 할 때, 한 줄에서 가능한 경우는 xx, ox, xo이다. 그리고 이 각각의 경우에 대해 optimization을 살펴본다. dp[i][0]을 i번째 줄이 xx일 때, 총 경우의 수, dp[i][1]을 i번째 줄이 ox일 때, 총 경우의 수, dp[i][2]을 i번째 줄이 xo일 때, 총 경우의 수라 하자. 이때 코드의 13~15행에 해당하는 optimal substructure를 통해 for문으로 dp배열을 채워나간다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 ..
[C++] 백준 14002번 : 가장 긴 증가하는 부분 수열 4 (G4)
#문제 www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net #풀이 & 학습한 내용 앞서 풀었던 supremo7.tistory.com/92에서 길이만을 구하는 것이 아닌 부분 수열 자체를 출력해줘야 한다. 이때는 추가로 dp배열에서 역추적하는 배열을 만들어 그 전의 index가 어디인지 저장한다. 그리고 재귀를 통해 출력해준다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 ..