정리용

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 1. 코드 설명 for _ in range(int(input())) : n = int(input()) arr = [1]*(n+4) arr[0] = 1 arr[1] = 1 arr[2] = 2 for i in range(n) : arr[i+3] = arr[i] + arr[i+1] print(arr[n-2]) 2. 주의사항 없다 시간 제한도 넉넉해서 for문 마다 리스트를 새로 만들수도 있으며 수열도 문제에..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 1. 코드 설명 from collections import deque n=int(input()) arr = [list(map(int, input())) for _ in range(n)] done =[[0] * n for _ in range(n)] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs (x,y,cnt) : q = deque() q.append((x,y)) ..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 1. 코드 설명 n = int(input()) dp = [0]*(n+1) dp[0] = 1 dp[1] = 3 for i in range(n-2): dp[i+2] = dp[i]*2 + dp[i+1] print(dp[n-1] % 10_007) 2. 주의 사항 11726 타일링 1과 똑같은 문제이다 n = 5나 6정도 까지 직접 구해가며 규칙을 찾으면 코드 자체는 아주 쉽다

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 1. 코드설명 n,m=map(int,input().split()) arr = [list(map(int, input())) for _ in range(n)] dx = [-1, 0, 1, 0] dy = [0, -1, 0, 1] done = [[0] * m for _ in range(n)] done[0][0] = 1 # 시작점 = 0, 0 from collections import deque q = deque([(0, 0)]) whi..

1. 코드 (실패) n= int(input()) dp = [[0]*9 for j in range(n+1)] dp[0] = [1]*9 for i in range(1,n) : for j in range(9): if j == 0 : dp[i][j] = dp[i-1][j-1] + i elif j == 8 : dp[i][j] = dp[i-1][j-1] else : dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] print(dp) print(dp[n-1]) print(sum(dp[n-1])%1000000000) 2. 주의사항 첫번째 자리를 기준으로 1~9으로 분류하여 규칙을 찾으려했으나 끝 자리 기준으로 0 의 규칙도 고려하여 규칙을 찾아야헀다 n = 5 까진 j==0 일떄 dp[i-1][j-..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 1. 코드 #import sys #input = sys.stdin.readline n=int(input()) dp = [0]*(n+2) lst=[0]*(n+2) for i in range(1,n+1): lst[i]=int(input()) dp[1] = lst[1] dp[2] = lst[1] + lst[2] #print(dp) for i in range( 3, n+1) : dp[i] = max(dp[..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1. 코드 설명 1) 전형적인 dp 풀이 ( 0 행렬을 만들고 채워가는 방식 ) n = int(input()) lst = list(map(int, input().split())) dp = [0] * n dp[0] = lst[0] print(dp) for i in range(1, len(lst)): dp[i] = max(lst[i], dp[i-1] + lst[i]) print(dp) print(max(dp))..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 1. 코드 설명 n = int(input()) tri =[list(map(int, input().split())) for _ in range(n)] #tri = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] #n=5 for i in range(1,n): for j in range(i+1): if j == 0: tri[i][j] = tri[i][j] + tri[i-1][j] #print('j == 0 ',tri) el..