🗂️ 문제링크: https://www.acmicpc.net/problem/11726 💡 접근법n=1일 때 직사각형을 채우는 방법은 1가지다.n=2일 때 직사각형을 채우는 방법은 2가지다.n=3일 때 직사각형을 채우는 방법은 3가지다.n=4일 때 직사각형을 채우는 방법은 5가지다.n=5일 때 직사각형을 채우는 방법은 8가지다. 이를 점화식으로 나타내면 dp[i] = dp[i-1] + dp[i-2] (N>2)이다. 😎 내 코드import sysn = int(sys.stdin.readline())dp = [0] * 1001dp[1] = 1dp[2] = 2for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2]print(dp[n]%10007) ✅ 정답 확인
🗂️ 문제링크: https://www.acmicpc.net/problem/1654 💡 접근법“N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.”라는 문제 조건에 따라 이분탐색의 기준을 필요한 랜선 개수 이상인지 이하인지 따라 범위를 좁혀나간다. 따라서 만들 수 있는 랜선의 수가 N개일 때 종료조건을 걸지 않고 계속해서 범위를 좁혀나가면서 최대의 랜선 길이를 구한다. 더이상 탐색 범위가 좁혀지지 않을때 high 값이 가장 긴 랜선의 길이가 되어 출력된다. 😎 내 코드import sysK, N = map(int, sys.stdin.readline().split())line = [int(sys.stdin.readline()) for _ in range(K)]def cal_line_num(heigh..
🗂️ 문제링크: https://www.acmicpc.net/problem/2805 💡 접근법N과 M의 범위가 크기 때문에 모든 경우의 수를 계산할 경우 시간초과가 발생한다. 절단 높이를 작게하면 가져가는 나무의 길이가 크고, 절단 높이를 크게하면 가져가는 나무 길이기 작다.이를 이용하여 절단 높이를 기준으로 이분 탐색을 수행한다. 또한 절단 높이를 최대로 하여 필요한 만큼의 나무를 가져가므로, 나무의 길이가 딱 떨어지지 않는 경우를 생각해야 한다. 이 경우엔 high(mid-1) 값을 출력하면 필요한 만큼 나무를 가져가면서 최대로 하는 절단 높이를 구할 수있다. 😎 내 코드import sysN, M = map(int, sys.stdin.readline().split())tree = list(map(..
🗂️ 문제 링크: https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 💡 접근법 1을 만드는 방법은 1가지이고, 2를 만드는 방법은 (1+1), (2)로 2가지이고, 3을 만드는 방법은 (1+1+1), (2+1)*2, (3)으로 4가지이고, 4를 만드는 방법은 (1+1+1+1), (1+1+2)*3, (1+3)*2, (2+2)로 7가지이고, 5를 만드는 방법은 (1+1+1+1+1), (1+1+1+2)*4, (1+2+2)*3, (3+1+1)*3, (3+2)*2로 13가지이다. 이를 점화식으로 나타내면 dp[i] = dp[i-1] + dp[i-2] +..
🗂️ 문제 링크: https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 💡 접근법 계단을 어떻게 올라갈까?가 아니라 계단을 어떻게 올라왔을까? 라는 관점에서 접근해야 한다. n번째 계단에 올라오기 위해서는 두 가지 경우가 있다. n-1번째 계단으로 오는 경우와 n-2번째 계단으로 오는 경우이다. n-1번째 계단으로 오는 경우에는 dp[n] = dp[n-3] + stairs[n-1] + stairs[n] 이다. n-2번째 계단으로 오는 경우에는 dp[n] = dp..
🗂️ 문제 링크: https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 💡 접근법 DP로 풀 수 있는지 먼저 확인한다. 부분 문제가 반복적으로 나타나야 한다. 부분 문제의 최적 결과를 사용하여 전체 문제의 최적 결과를 낼 수 있다. DP 테이블을 초기화한다. 조건에 맞는 점화식을 구한다. 😎 내 코드 import sys def fib_recur(n): global recur_cnt if n == 1 or n == 2: recur_cnt..
🗂️ 문제 링크: https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 💡 접근법 부등호 기호 앞뒤에 넣을 수 있는 숫자 0~9를 갖는 nums 리스트로 생성한다. permutations를 활용하여 K+1자리수에 해당하는 순열들을 생성한다. 부등호에 따라 값을 비교하고 비교 결과가 옳지 않을 경우에는 break문을 통해 for 문을 빠져나온다. is_valid 변수를 활용하여 true일 경우, 즉 부등호에 따라 비교 결과가 옳은 순열에 대해서만 answers에 ..
🗂️ 문제 링크: https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 💡 접근법 단어의 알파벳 하나하나를 스택의 마지막 요소와 비교한다. 이때 같을 경우 스택의 마지막 요소를 pop하고, 같지 않을 경우 알파벳을 스택에 append한다. 알파벳을 모두 순회하고 결과적으로 스택이 비어있다면 좋은 단어로 판단할 수 있다. 😎 내 코드 import sys N = int(sys.stdin.readline()) words = [] for _ in range(N): w..
