몽상실현개발주의

[BOJ] 2186 / 문자판 / Python 파이썬 https://www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 풀이 주어진 조건을 만족하는 모든 경로의 개수를 구하는 문제이다. 모든 경로는 DFS 를 이용하여 구현하였지만, 시간초과에 부딪히고 말았다. 모든 경로에 대한 완전탐색의 최적화는, 각 진행상황에 대해 memorization 을 해주며 중복하여 탐색하는 경우를 제거해 주어야 하였다. 그래서 visited를 2..

[BOJ] 9095 / 1, 2, 3 더하기 / Python 파이썬 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 주어진 숫자를 1, 2, 3 으로 표현하는 경우의 수는 점화식으로 표현 가능하다. dp(1) = 1 dp(2) = 2 dp(3) = 4 dp(4) = dp(1) + dp(2) + dp(3) dp(N) = dp(N-3) + dp(N-2) + dp(N-1) N = int(input()) nums = [0, 1, 2, 4] for _ in range(4, 12): nums.append(sum(nums[-3:])) for _ in..

[BOJ] 11052 / 카드 구매하기 / Python 파이썬 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 현재 index 까지의 부분 list 의 모든 경우의 수 중 가장 큰 경우를 구하여, 전체 경우에서의 가장 큰 값의 경우를 구하는 문제이다. [BOJ] 1699 / 제곱수의 합 / Python 파이썬 과 비슷한 유형의 문제 N = int(input()) Cards = [0] + list(map(int, input().split())) d..

[BOJ] 2011 / 암호코드 / Python 파이썬 https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 풀이 암호 코드의 길이와 만들어지는 수에 따라 조건을 달리하여 경우의 수를 구하는 문제이다. 첫번째 자리의 암호 코드는 '0' 이 아닐때 1이 된다 i 번째 자리의 암호 코드 i 번째 숫자가 '0' 이 아닐 시, i-1 번째 경우의 수와 같다. i-1, i 번째 숫자를 두 자리 수인 하나의 숫자로 보았을 때, 10 ~ 26 이라면 i-2 의 경우의 수를 더해준..

[BOJ] 9461 / 파도반 수열 / Python 파이썬 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 기본적인 점화식 풀이 문제 이다. N = 1 -> 1 N = 2 -> 1 N = 3 -> 1 N = 4 -> 2 N = 5 -> 2 N = 6 -> 3 N = 7 -> 4 N = 8 -> 5 N = 9 -> 7 점화식은 N > 5 일때 부터 적용 된다. dp(N) = dp(N-1) + dp(N-5) (N > 5) T = int(input(..

[BOJ] 2133 / 타일 채우기 / Python 파이썬 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 풀이 경우의 수를 구하고, 점화식을 찾아 풀어 보았다. 블럭 문제의 경우 N 과 N-1 사이의 관계가 명확한 경우의 문제가 많으므로 점화식을 이용하여 간단히 풀 수 있는 것같다. N = 0 -> 1 N = 1 -> 0 N = 2 -> 3 N = 3 -> 0 N = 4 -> 11 N = 5 -> 0 N = 6 -> 41 N = 7 -> 0 1 3 11 41 .... 2 8 30 2 = 1 * 2 8 = (3 + 1) * 2 30 = (11 + 3 + ..

[BOJ] 1699 / 제곱수의 합 / Python 파이썬 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 풀이 주어진 숫자와 제곱수와의 차이를 생각하는것이 문제의 해결 방법이었다. N = 1 -> 1 -> 1 N = 2 -> 1 + 1 -> 2 N = 3 -> 1 + 1 + 1 -> 3 N = 4 -> 2 -> 1 N = 5 -> 2 + 1 -> 2 N = 6 -> 2 + 1 + 1 -> 3 N = 7 ..

[BOJ] 2579 / 계단 오르기 / Python 파이썬 https://www.acmicpc.net/submit/2579/29254021 로그인 www.acmicpc.net 풀이 [BOJ] 2156 / 포도주 시식 과 유사한 문제이다. 포도주 시식 문제의 경우 마신다/마시지 않는다의 경우로 선택하지 않는 경우가 있지만, 이 문제의 경우 해당 index 의 계단을 밟지 않는 경우가 없어 고려되지 않는다. 그래서 현재 index 의 계단을 밟는 경우는 두가지가 된다. i-2 i-1 i ~ O X O ~ X O O N = int(input()) nums = [] for _ in range(N): nums.append(int(input())) dp = [0] * N dp[0] = nums[0] if N > 1..