알고리즘 풀이/백준

백준 1149번 : RGB거리 (Python)

문제 : www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 다른 사람의 풀이를 참고했다. dp에 값을 1개씩이 아닌 3개씩 저장한다. 반복문을 돌며 해당 위치(i)에서 R,G,B 로 각각 칠했을 때를 dp에 리스트로 저장한다. 즉 dp에는 지금까지 더한 값(dp) 중 i-1에서 R위치를 제외하고 가장 작은 값 + i에서 R로 칠할 경우를 B, G도 똑같이 수행한뒤 추가한다. n = int(input()) cost = [] for i ..

백준 2193번 : 이친수 (Python)

문제 : www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 맨앞의 수는 무조건 1이다. 그 다음부터는 1이 연속 두번 이상 나오는 경우를 제외해야 하므로 남은 자리에 수를 대입할 때 1과 0을 대입하지 않고 01과 0을 대입하는 것으로 계산한다. 01은 자리를 한번에 두개씩 차지하므로 01이 들어가는 만큼 빈자리의 수를 줄이고 조합으로 해결한다. 우선 맨 앞자리 수는 고정이므로 빈자리의 수 n-1을 k에 저장한다. 01이 들어가는 수 만큼 반복..

백준 14501번 : 퇴사 (Python)

문제 : www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 리스트 A에 입력받은 값을 저장한다. 시작 날짜 인덱스에 [끝나는 날짜, 금액] 을 저장하도록 했다. dp에 수익을 저장하도록 한다. 이중 포문중 바깥포문은 A 리스트를 인덱스 i로 방문한다. 안 포문은 i부터 끝까지 dp를 방문하며 i일 현재 수익 + i상담의 수익이 i일 상담이 끝나는 날의 현재 수익보다 크다면 큰 값으로 변경한다. 가장 큰 수익을 출력한다. n = int(input()) A = [[]] for i in range(1,n+1): A.append(list(map(int, input().split(" ")))) A[i..

백준 11712번 : 2×n 타일링 2 (Python)

문제 : www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 기본적으로 타일을 나누어야 할 단위는 2*2 모양이다. 2*2 크기에 타일링이 가능한 경우의 수는 3이다. 하지만 이 경우 1*2 + 2*_인 경우만 고려되고 2*_ + 1*2인 위 그림과 같은 경우를 고려하지 못한다. 따라서 위 경우는 2가지가 가능하므로 n-3의 경우의 수에 2를 곱한값을 더해준다. n = int(input()) dp = [0, 1, 3, 5] for i in range(4, n+1): dp.append((..

백준 1010번 : 다리 놓기 (Python)

문제 : www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 m개의 사이트 중 순서없이 n개를 뽑는 경우의 수를 계산하면 된다. 예를 들어 m=5, n=2 라고 가정하면 5*4 / 2*1 이다. 이는 5*4 = 5*4*3*2*1 / 3*2*1 이므로 5*4*3*2*1 / ((3*2*1) * (2*1)) 로 표현이 가능하다. dp에 해당 인덱스까지의 모든 숫자의 곱을 저장해둔다. 그 뒤 dp[m]을 dp[m-n]*dp[n]의 값으로 나눠 출력한다. t = i..

백준 9461번 : 파도반 수열 (Python)

문제 : www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 dp에 P(n)의 값을 저장한다. n이 5 이상이 되면 해당 값은 P(n-5)+P(n-1)의 값을 가진다. t = int(input()) dp = [0, 1, 1, 1, 2] for _ in range(t): n = int(input()) if n > len(dp)-1: for i in range(len(dp),n+1): dp.append(dp[i-5]+dp[i-1]) print(dp[n])

백준 1932번 : 정수 삼각형 (Python)

문제 : www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 바로 너비우선탐색으로 풀다 바꿔 풀었다. dp에 해당 위치까지의 최대값을 저장한다. a에 왼쪽 위를 더한값과 오른쪽 위를 더한값을 추가하여 둘중 최대값을 해당 위치 값으로 저장한다. 왼쪽 위와 오른쪽 위를 더할 때 범위가 벗어나지 않도록 조건문을 걸어준다. n = int(input()) A = [] for i in range(n): temp = list(map(int, input().split(" "))) A.append(temp) dp = [] for i in ran..

백준 2156번 : 포도주 시식 (Python)

문제 : www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 A에 포도주 양을 입력받는다. dp에 해당 위치 포도주를 마셨을 경우의 최대 양을 저장한다. 연속 3잔을 마실 수 없으므로 가능한 경우는 ① 현재 포도주 + 현재-2 까지의 dp중 최대값 (1개 연속) ② 현재 포도주 + 현재-1 포도주 + 현재-3 까지의 dp중 최대값 (2개 연속) 이렇게 두가지이다. 최종적으로 가장 큰 dp값을 출력한다. n = int(input()) A = [] for i i..

백준 11053 : 가장 긴 증가하는 부분 수열 (Python)

문제 : www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 조금 찾아봤다. 쉬운 문제였다. A에 수를 입력받고 dp에 해당 위치까지 가장 긴 부분 수열을 저장한다. i번째의 수를 포함한 dp는 i보다 작은 위치를 확인하며 [본인보다 작은 A값의 dp중 가장 큰 dp + 1 ]을 한 값이다. n = int(input()) A = list(map(int, input().split(..

백준 11726번 : 2xn 타일링 (Python)

문제 : www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 dp에 2x1부터 경우의 수를 입력한 뒤 입력된 수를 참고하여 다음 2xn 크기의 타일링을 계산한다. 현재 주어진 타일로 겹치지 않게 가장 작게 사각형을 채우는 방법은 ①세로 타일 하나로 2x1 만들기 ②가로 타일 두개로 2x2 만들기 이다. ex) 세로 타일 두개로 2x2를 만드는 경우는 ①의 경우에 속하므로 겹치는 경우이다. 따라서 2xn 타일링 경우의 수는 [ 2x(n-1)에 ①을 붙이는 경우 + 2x(n-2)에..