algorithm
-
[Python]백준 1309/동물원/dpalgorithm/문제 2022. 3. 3. 22:16
https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net ⚡️ 문제 설명 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램 ⚡️ 해결 방법 #왼쪽에 있는 경우 dp[i][0]=(dp[i-1][1]+dp[i-1][2])%9901 #오른쪽에 있는 경우 dp[i][1]=(dp[i - 1][0] + dp[i - 1][2])%9901 #둘다 없는 경우 dp[i][2]=(dp[i - 1][0]+ dp[i - 1][1] + dp[i - 1][2])%9901 🟢 왼쪽에 있는 경우 = 전단계에서 오른쪽에 있는 경우 ☑️ + 그 전단계에서 둘다 없는 경우 dp[i][0]=(dp[..
-
[Python]백준 2579/계단오르기/dpalgorithm/문제 2022. 3. 3. 00:30
https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net ⚡️ 문제 설명 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램 ⚡️ 해결 방법 dp[..
-
[Python]백준 2644/촌수계산/dfs/bfsalgorithm/문제 2022. 2. 27. 12:05
https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net ⚡️ 문제 설명 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. ⚡️ 해결 방법 visited 배열은 촌수를 계산할 때 사용할 것이다. 입력받은 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때는 -1을 출력해야 한다. 그러므로 초기 배열을 -1로 해준다. 그리고 처음시작하는 자기자신을 0으로 바꿔준..
-
[Python]백준 11726번/2×n 타일링/dpalgorithm/문제 2022. 2. 23. 17:16
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ⚡️ 문제 설명 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. ⚡️ 해결 방법 ⚡️ 코드 import sys input=sys.stdin.readline n=int(input()) dp=[0]*(n+1) for i in range(1,n+1): if(i==1): dp[i]=1 elif(i==2): dp[i]=2 else: dp[i]=dp[i-1]+dp[i-2] pri..
-
[Python]백준 1541번/잃어버린 괄호/greedyalgorithm/문제 2022. 2. 23. 11:59
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net ⚡️ 문제 설명 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램 ⚡️ 해결 방법 이 입력을 예시로 설명해보면 55-50+40 1. -기준으로 나누기 n = input().split('-') 2. 1.에서 -를 기준으로 나누었을 때 첫번째 숫자들 모두 더하기 for i in n[0].split('+'): sum += int(i) 3. 1.에서 -를 기준으로 나누었을 때 뒤에 있는 숫자..
-
[Python]백준 1339번/단어수학/greedyalgorithm/문제 2022. 2. 22. 12:04
https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net ⚡️ 문제 설명 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = ..
-
[Python]백준 12865번/평범한 배낭/dpalgorithm/문제 2022. 2. 20. 12:38
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net # 문제 설명 첫 줄 : 물품의 수 N(1 ≤ N ≤ 100), 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000) 두번째 줄~N개의 줄 : 물건의 무게 W(1 ≤ W ≤ 100,000), 해당 물건의 가치 V(0 ≤ V ≤ 1,000) 배낳에 넣을 수 있는 물건들의 가치의 최댓값 구하기 # 해결 방법 dp 는 N(1~N)번째 물..
-
[Python]백준 1149번/RGB거리/dpalgorithm/문제 2022. 2. 20. 00:21
# 문제 설명 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 ..