Problem Solving/Baekjoon
-
[백준] 14002번 문제 (가장 긴 증가하는 부분 수열 4) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 19. 15:04
n = int(input()) nums = list(map(int, input().split())) dp = [1] * n for i in range(n): for j in range(i): if nums[i] > nums[j]: dp[i] = max(1 + dp[j], dp[i]) result = [] max_num_dp = max(dp) print(max_num_dp) for i in range(n-1, -1, -1): if dp[i] == max_num_dp: result.append(nums[i]) max_num_dp -= 1 [print(i, end=" ") for i in reversed(result)] https://honggom.tistory.com/80 [백준] 11053번 문제 (가장 ..
-
[백준] 11727번 문제 (2 x n 타일링 2) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 19. 14:52
n = int(input()) dp = [0, 1, 3, 5] for i in range(4, 1001): dp.append((dp[i - 2] * 2) + dp[i - 1]) print(dp[n] % 10007) https://honggom.tistory.com/84 [백준] 11726번 문제 (2 x n 타일링) 파이썬(Python) 풀이 n = int(input()) dp = [0, 1, 2] for i in range(3, 1001): dp.append(dp[i - 2] + dp[i - 1]) print(dp[n] % 10007) 처음에는 도대체 어떻게 풀어야 하나... 고민이 많았는데 참 단순한 문제였다. 직접 메모장.. honggom.tistory.com 앞서 풀이한 문제(위 링크)와 매우 유..
-
[백준] 11726번 문제 (2 x n 타일링) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 19. 14:33
n = int(input()) dp = [0, 1, 2] for i in range(3, 1001): dp.append(dp[i - 2] + dp[i - 1]) print(dp[n] % 10007) 처음에는 도대체 어떻게 풀어야 하나... 고민이 많았는데 참 단순한 문제였다. 직접 메모장에 경우의 수를 그려가며 직사각형을 채우는 방법의 수를 구해보면 알 수 있는데 n을 기준으로 1개면 : 1 2개면 : 2 3개면 : 3 4개면 : 5 5개면 : 8 6개면 : 13 7개면 : 21 8개면 : 34 9개면 : 55 방법의 수가 나온다. 그러면 숫자의 규칙이 보일 것이다. 바로 dp[i] = dp[i - 1] + dp[i - 2] 라는 규칙이 성립되고, 이것을 for문을 반복하며 n번 까지의 방법의 수를 구하..
-
[백준] 11057번 문제 (오르막 수) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 19. 14:11
dp = [[0] * 10 for i in range(1001)] n = int(input()) for i in range(10): dp[1][i] = 1 for i in range(2, n + 1): for j in range(10): if j == 0: dp[i][j] = 1 else: dp[i][j] = dp[i-1][j] + dp[i][j-1] print(sum(dp[n]) % 10007) 우선 경우의 수를 메모장에 적어가며 규칙을 찾았다. 규칙은 해당 자리수의 숫자가 오르막 수일 때 맨 뒤에 오는 숫자에 대해 사용된 횟수를 적으면 알 수 있다. 그것을 표로 나타내면 아래와 같다. 0 1 2 3 4 5 6 7 8 9 자리수 1 1 1 1 1 1 1 1 1 1 1 자리수 2 1 2 3 4 5 6 7..
-
[백준] 11055번 문제 (가장 큰 증가 부분 수열) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 19. 13:49
n = int(input()) nums = list(map(int, input().split())) dp = nums[:] for i in range(n): for j in range(i): if nums[i] > nums[j]: dp[i] = max(nums[i] + dp[j], dp[i]) print(max(dp)) https://honggom.tistory.com/80 [백준] 11053번 문제 (가장 긴 증가하는 부분 수열) 파이썬(Python) 풀이 n = int(input()) nums = list(map(int, input().split())) dp = [1] * n for i in range(n): for j in range(i): if nums[i] > nums[j]: dp[i] = ma..
-
[백준] 11053번 문제 (가장 긴 증가하는 부분 수열) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 19. 13:33
n = int(input()) nums = list(map(int, input().split())) dp = [1] * n for i in range(n): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[j] + 1, dp[i]) print(max(dp)) dp문제이며, 직관적으로 풀 수 있는 문제다. for문이 이중으로 있는데, 바깥 for문은 0 ~ n - 1까지 반복되고, 안쪽 for문은 0 ~ 바깥 for문의 인덱스 - 1까지 반복된다. 그러면서 nums[i] > nums[j] 가 성립되면 dp[i]에 dp[j] + 1을 할당하며 수열의 크기를 점진적으로 더하며 구한다.
-
[백준] 11052번 문제 (카드 구매하기) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 19. 13:16
n = int(input()) dp = [0] * (n + 1) prices = [0] + list(map(int, input().split())) dp[1] = prices[1] for i in range(2, n + 1): for j in range(1, i + 1): dp[i] = max(dp[i], dp[i - j] + prices[j]) print(dp[n]) 문제가 너무 길어서 읽고 이해하는데 시간이 좀 걸린다. 전형적인 dp 문제이며 이중 for문을 통해 풀 수 있었다. 카드를 n개 구매하는 경우의 최대 금액을 dp에 index와 숫자를 일치 시켜서 dp에 할당을 해준다. 카드를 1개 구매하는 경우의 최대 금액은 당연하게도 카드를 1개 구매하는 것이다. 카드를 2개 구매하는 경우의 최대 금액..
-
[백준] 10844번 문제 (쉬운 계단 수) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 19. 11:56
n = int(input()) dp = [[0 for i in range(10)] for j in range(101)] for i in range(1, 10): dp[1][i] = 1 for i in range(2, n + 1): for j in range(10): if j == 0: dp[i][j] = dp[i - 1][1] elif j == 9: dp[i][j] = dp[i - 1][8] else: dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] print(sum(dp[n]) % 1000000000) 언제나 dp문제는 경우의 수를 직접 메모장에 써보며 푸는 방법이 좋은 것 같다. 경우의 수를 적다보면 각 자리수에서 맨 뒤 자리에 오는 수의 개수가 규칙이 있다는 것을..
-
[백준] 2579번 문제 (계단 오르기) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 19. 11:32
n = int(input()) steps = [0 for i in range(301)] for i in range(n): steps[i] = int(input()) dp = [steps[0]] + [0 for i in range(300)] dp[1] = steps[0] + steps[1] dp[2] = max(steps[1] + steps[2], steps[0] + steps[2]) for i in range(3, n): dp[i] = max(dp[i - 3] + steps[i - 1] + steps[i], dp[i - 2] + steps[i]) print(dp[n - 1]) dp에 해당 계단을 밟았을 때 최대의 점수를 저장한다고 생각하고 풀면 좀 더 쉽게 접근할 수 있을 것 같다. 아래 dp를 순회하는..