https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net dp = [0] * 1001 dp[1] = 1 dp[2] = 3 for i in range(3,1001): dp[i] = dp[i-1] + dp[i-2] * 2 n = int(input()) print(dp[n] % 10007) https://cijbest.tistory.com/21 [백준 11727 : PYTHON] 2xn 타일링 2 문제 풀기 : 11727번 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net dp = [0] * 13 dp[1] = 1 dp[2] = 2 dp[3] = 4 for i in range(4,11): dp[i] = dp[i -3] + dp[i-2] + dp[i-1] t = int(input()) for _ in range(t): n = int(input()) print(dp[n]) dp 중 메모지에이션을 이용하여 풀었다. dp는 진짜 아이디어가 생각이 안나면 진짜 안풀리는거 같다. 이 문제의 풀이는 1 = 1 2 = 1+1 = 2 3 = 1 + 1 + 1 = 1 + 2 = 2..

https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net import sys from collections import deque def bfs(x, y, num): q.append([x, y]) cnt = 0 while q: x, y = q.popleft() for i in range(4): nx, ny = x + dx[i], y + dy[i] if 0

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net import sys n,m = map(int,sys.stdin.readline().split()) graph = [] for i in range(n): graph.append(list(map(int,sys.stdin.readline().split()))) tetrominoes = [ [(0,0), (0,1), (1,0), (1,1)], # ㅁ [(0,0), (0,1), (0,2), (0,3)], ..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 전형적인 이분 탐색 문제이지만 약간 문제를 읽어보면 다르다는걸 알수 있다. ' 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다. ' 최댓값을 뽑아내기 위해서 result라는 값을 만들었다. import sys n, m = map(int,sys.stdin.readline().split()) tree = list(m..

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net import sys n = int(sys.stdin.readline()) num_list = list(map(int,sys.stdin.readline().split())) lis = [0] for num in num_list: # lis 마지막 값보다 현재 num 값이 크다면 그냥 lis에 넣는다. 왜냐 최장 증가 수열이니까 큰값이면 우선 넣음 if lis[-1] < num: lis.append(..

LIS란 가장 긴 증가하는 부분 수열을 나타낸다. 주어진 수열 리스트를 가장 길게 만드는 것이다. LIS를 풀기위한 가장 일반적인 방법은 DP 이다. ex) n = int(input()) num = list(map(int, input().split())) num_len = [1 for i in range(n)] for k in range(1,n): for j in range(k): if num[j] < num[k]: num_len[k] = max( num_len[k],num_len[j]+1) print(max(num_len)) 위 알고리즘의 시간복잡도는 O(n^2)을 갖게 된다. 첫번째 요소부터 k 번째 요소까지 비교를 한 후 뒤에 있는 요소가 num[k] 가 더 크다면 k까지의 최장 값을 현재값과 j번..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 이 문제는 다익스트라를 이용한 최단 경로 문제이다. 이문제의 특성이라면 최단 경로로 갔다가? 다시 돌아와야한다 이러한 점만 고려하면 기본적인 다익스트라 알고리즘에 문제의 조건에만 맞게 해주면 해결 가능하다. import sys import heapq n, m, x = map(int, sys.stdin.readline().split()) graph = [[] for _..