[Coding Test]/[백준]

[백준] 2579 파이썬(python) : 계단 오르기

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net import sys n = int(sys.stdin.readline()) arr = [0]*(301) #1 dp = [0]*(301) for i in range(n): arr[i] = int(sys.stdin.readline()) #2 dp[0] = arr[0] dp[1] = arr[0] + arr[1] dp[2] = max(arr[1]+arr[2], arr[0]+arr[2]) #3 for i in range..

[백준] 1932 파이썬(python) : 정수 삼각형 - (★)

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 각 행의 첫번째 원소와 마지막 원소는 그 바로위 원소들을 더해주면 되고 나머지들은 바로 위 2개의 원소들 중 큰 수를 더해준다. import sys n = int(sys.stdin.readline()) graph = [ list(map(int, input().split())) for _ in range(n)] for i in range(1, n): #1 for j in range(len(graph[i])): #2 if j == 0: #3 graph[i][j] = gra..

[백준] 1149 파이썬(python) : RGB거리

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net import sys n = int(sys.stdin.readline()) dp = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ] for i in range(1, n): #1 dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + dp[i][0] dp[i][1] = min(dp[i-1][..

[백준] 1912 파이썬(python) : 연속합

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 예제 1) 10 -4 3 1 5 6 -35 12 21 -1 10 6 9 10 15 21 -14 12 33 32 연속된 몇개의 수를 더해서 최대값을 출력하는것이 문제의 요구사항이니까 현재위치에서 음수가 나왔을때 이전 인덱스까지의 dp와 더할때 0 밑으로 내려가 음수가 되는지 확인해야 한다. 더한 값이 음수가 된다면 연속된 합을 유지할 수 없다. 하지만 더했을때 음수가 아니고 그 다음 위치의 값을 더해줌으로써 ..

[백준] 9461 파이썬(python) : 파도반 수열

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 숫자가 1 1 1 2 2 3 4 5 7 9... 순서로 진행되는데 i-3번째와 i-2번째 숫자를 더해서 i번째 숫자를 만들 수 있다. 점화식을 세우면 dp[i] = dp[i-3] + dp[i-2] 가 된다. import sys t = int(sys.stdin.readline()) for _ in range(t): #1 n = int(sys.stdin.readline()) #2 dp = [0]*(101)..

[백준] 1904 파이썬(python) : 01타일 - dp기초

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net dp의 대표적인 유형인 타일 문제이다. n이 입력되었을때 타일 00과 1을 이용하여 길이 n의 타일을 만들 수 있는 경우의 수를 구하는 문제다. dp를 사용하면 시간 복잡도 O(N)으로 해결할 수 있다. 타일은 1 과 00만 사용할 수 있으므로 n = 1일때는 1 -> 1가지 n = 2일때는 00 -> 1가지 n = 3일때는 001, 100, 111 -> 3가지 n = 4일때는 0011, 0000, 1..