꾸준하게 거북이처럼

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 가장 긴 증가 부분 수열을 찾는 것으로, 각 수열 요소보다 작은 요소들의 수열 길이 중 가장 큰 것 +1 을 하는 방식으로 문제를 풀 수 있다. arr 10 20 10 30 20 50 dp 1 2 1 3 2 4 주어진 수열에서 증가수열 & 수열의 길이가 최대가 되어야한다. 그렇다면 dp를 이용해서 현재까지 가장 수열의 길이가 큰 것을 차근차근 구하고, 이를 배열에 저장한다. 현재 요소보..

10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 최근 DP 문제를 풀기 시작했고, 점화식 찾는데 익숙하지 않아서 1시간 이상 붙잡다가 매번 문제풀이를 봤다.. 문제는 풀 때 최대 1시간 ~ 1시간 반까지만 생각하고 풀이가 떠오르지 않으면 문제 풀이를 찾아보는 식으로 스스로 정했다. 이번에는 꼭 뭔가 풀 수 있을 것 같다는 생각이 들어 1시간 반 가까이 생각해서 이전에 풀었던 문제풀이를 활용해서 문제를 풀 수 있었다. 2차원 배열을 이용하는 것이다. d[i][j] : 자리수가 i(1개 ~ 100개) 개인 수에서 마지막 자리수가 j ( 0 ~ 9까지) 로 끝나는 계단 수가 총 몇 개인지 의미. 즉 d[i] 는 자리수가 i 개인 ..

15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 1차원 배열로 접근해서 문제를 풀기 힘들다. 아직 1차원으로 푸는 문제 밖에 만나지 못해서 생각도 하지 못했다. 핵심 점화식 알기 dp[ i ][ j ]: i 를 1,2,3 의 합으로 나타낸 개수 중, j (1 또는 2 또는 3) 로 끝나는 합의 개수( 연속 사용X) 동적 프로그래밍의 방식의 큰 특징인 작은 문제를 이용해서 큰 문제를 해결하는 방법처럼! 초기 값 부터 차근차근 배열을 이용해서 값을 저장해서 구하고자 하는 수 n을 1,2,3 수의 합으로 나타낼 수 있는 개수를 구할 수 있다. 초기부터 쭉 ..

11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net dp문제는 작은 문제로 나누어 큰 문제를 풀 수 있는 방식일 때, 문제를 해결할 수 있게 된다. -> n이 1 일때부터 차근차근 점화식을 만들어 나가면 된다. dp 라는 배열이 i개 카드를 구매하는 방법 중 최대값을 나타내고, p가 해당 개수 카드팩의 가격을 나타낸다면 dp[1] = p[1] dp[2] = dp[1] + p[1] or p[2] dp[3] = dp[2] + p[1] or dp[1] + p[2] or p[3] .... 이와 같은 점화식을 만들 수 있다. 이는..

11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 이 문제는 점화식 또는 규칙을 찾으면 풀 수 있는 문제다. 2 x 1 : ㅡ (1 가지) 2 x 2: ㅁ , = , ㅣㅣ(3 가지) 2 x 3: lll, l=, =l, ㅁl, lㅁ ( 5 가지 ) 2 x 4: llll, ll=, l=l, =ll, ==, ㅁㅁ, ㅁll, ㅁ=, lㅁl, llㅁ, =ㅁ ( 11 가지 ) 나는 다른 풀이와는 다르게 n 이 홀수 일 때, d[n] = d[n - 1] * 2 - 1 n 이 짝수 일 때, d[n] = d[n - 1] * 2 + 1 로 점화식을 구했다. 하..

1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 처음에 문제를 풀고 런타임 에러가 났다. 그 이유는 입력조건이 1보다 크거나 같은!!! 수에서 100만 보다 작은 수가 입력 인데 1보다 큰 것으로 잘못보고 지나쳤다. 1을 입력하니 에러가 났다. 이전 코드 n = int(input()) d = [0] * (n+2) d[2] = 1 d[3] = 1 if n == 2 or n == 3: print(d[n]) exit(0) else: for i in range(4, n + 1): a = 1000000 b = 1000000 c = 1000000 if i % 2 == 0: a = d[i // 2] + 1 if i % 3 == 0: b..