문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 이 문제에서 n의 제한은 1000이다. 따라서 O(n^2) 풀이가 가능한것을 인지하고 있자. 증가하는 수열이므로, 특정 인덱스 앞의 요소들을 하나씩 다 살펴본다. 1) 이후 만약 값이 나보다 작고 2) 해당 값에 저장된 수열 + 1 (현재 인덱스까지 포함하면 + 1 이니까 ) , 현재 수열의 길이를 비교해서 ..

문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 2 x n 타일링 문제와 거의 유사하다. (풀이 링크 : https://whiporithm.tistory.com/6 ) 차이점이라고는 2 * 2 타일이 하나 더 들어온 것. 따라서 = 타일이 ㅁ 타일이 될 수 있다. 그렇기에 경우의 수를 2배로 설정해주면 답이 나온다. 코드 n = int(input()) d = [0] * 1001 d[1] = 1 d[2] = 3 for i in range(3, 1001): d[i] ..

문제 (S3) https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 DP의 정수, 타일링 문제이다. 예전에도 풀었지만 100프로 이해한다는 느낌이 아니었는데, 이 참에 다시 풀어봤다. 우리는 1*2 의 타일과 ( ㅡ ) 2 * 1 타일을 사용할 수 있다. ( | ) 해당 타일들을 이용하여 2 * n 의 타일을 채워야한다. 여기서 우선 생각해야할것중 하나는 1 * 2 타일을 사용하기 위해서는 항상 2개를 세트로 사용해야한다. ( = ) 경우의 수를 생각해보면 Case..