백준 1149_RGB 거리 조건 집이 N개가 있고, 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각 집을 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하라. 1번 집의 색은 2번 집의 색과 같지 않아야한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i (2

http://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net # 조건 수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열을 구하라 # 접근 방법 이전의 하위 문제처럼 DP를 이용하여 이전 값들을 모두 순회한다면 수열 A의 크기 1,000,000 이하 이므로 시간초과가 난다. 따라서, 현재 값들을 dp테이블에 추가해주며, dp에서 가장 큰 수보다 크다면 append, 아니라면 들어갈 수 있는 자리를 찾아서 넣어준다. 찾는 모듈은 bisect를 이용해준다. im..

http://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가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하라 A = {10, 20, 10, 30, 20, 50} 인 경우 가장 긴 증가하는 부분 수열은 10, 20, 30, 50 이고 길이는 4이다. # 접근 방법 dp를 이용해준다. 현재 인덱스의 숫자를 기준으로 이전의 숫자를 모두 훑어 준다. 1번부터 채워가..

http://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net # 조건 n가지 종류의 동전이 있고 각각의 동전이 나타내는 가치는 다르다. 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶을 때, 그 경우의 수를 구하시오 각 동전은 몇 개라도 사용 가능하다. 동전의 구성이 같은데, 순서만 다른 것은 같은 경우 # 접근 방법 다이나믹 프로그래밍을 이용해서 풀어주면 될 것 같다. 가치의 합 +1 만큼의 dp테이블을 만들어 주고 각 가치를 만들 수 있는 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # 조건 가장 왼쪽 위, 집의 좌표 (1,1) 가장 오른쪽 아래, 학교의 좌표 (m,n) 격자의 크기 m,n과 물이 잠긴 지역의 좌표 담은 2차원 배열 puddles가 매개변수 오른쪽과 아래쪽으로만 움직일 수 있으며 학교까지 갈 수 있는 최단 경로의 개수를 1,000,000,007로 나눈 나머지를 return 하여라 # 접근 방법 현재 칸에 올 수 있는 경로의 수 -> 왼쪽과 위쪽칸의 합과 같다...

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 조건 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임 계단을 밟으면 해당 계단에 쓰여 있는 점수를 얻게 된다. 아래 규칙을 지켜서 얻을 수 있는 점수의 최댓값을 구하라 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net # 조건 2xN 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램 작성 방법의 수를 10,007로 나눈 나머지를 출력하라. # 접근 방법 규칙을 찾는 것이 좋을 것 같다. n = 1 인 경우 1가지 n = 2 인 경우 2가지 n = 3 인 경우 3가지 n = 4 인 경우 5가지 n = 5 인 경우 8가지 f(n) = f(n-2) * 2 + f(n-3) 으로 구할 수 있다. 또는 f(n) = ..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net # 조건 피보나치 함수는 f(n ) = f(n-1) + f(n-1)의 성질을 가진다. 정수 n이 주어졌을 때 0과 1이 몇 번 출력되는지 구하여라. # 접근 방법 문제에 주어진대로 재귀를 이용하여 구해봤지만 역시나 시간초과. 메모이제이션을 이용해봐도 시간초과가 나게 되었다. 0과 1이 출력되는 횟수가 수가 증가함에 따라 각각 피보나치 함수와 동일하게 출력됨을 발견 따라서 dp table을 따로 만들어 준 후 입력 n에 대해 횟수를 출력시켜준다. # 시간초과 코드 def fibo(n): glob..

백준 5557_1학년 # Problem 줄 지어있는 숫자 들이 있을 때 아래의 조건을 지키며 등식을 완성하여라 마지막 두 숫자 사이에는 '=', 나머지 숫자 사이에는 '+'또는 '-' 이 때, 왼쪽부터 계산을 할 때, 중간 결과값이 모두 0이상 20이하여야 한다. 올바른 등식의 수를 구하는 프로그램 작성 # 접근 방법 모든 경우의 수를 구하게 되면 2^100의 경우의 수가 생기므로 dp로 풀어야 될 것 같다. bottom-up 방식으로 DP TABLE 이용 DP TABLE의 경우 최댓값이 20이 넘어가면 안된다는 조건이 있기 때문에 21개만 만들어주면 된다. 점화식 equation[i][j+number[i]] += equation[i-1][j] equation[..