백준, boj) 2624. 동전 바꿔주기
1. 문제 링크 https://www.acmicpc.net/problem/2624 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다. 20 = 10×2 20 = 10×1 + 5×2 20 = 10×1 + 5×1 www.acmicpc.net 2. 문제 개요 지폐의 금액과 동전의 가짓수, 금액과 개수가 주어질 때, 지폐의 금액인 T를 바꿔줄 수 있는 가짓수를 출..
백준, boj) 2157. 여행 (C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1≤N≤300), M(2≤M≤N), K(1≤K≤100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1≤a, b≤N, 1≤c≤10,000)가 주어진다. 이는 a번 도시에서 b번 도시로 이동하는 항로가 있고, 서비스되는 기내식의 점수가 c점이라는 의미이다. 서쪽에서 동쪽으로 이동하는 항로가 입력될 수도 있고, 같은 도시 쌍 사이에 항로가 여러 개 있을 수도 있 www.acmicpc.net 2. 문제 개요 M개 이하의 도시를 지나는 여행을 계획하려 한다. 여행경로는 반드시 1번 도시에서 시작해서 N번 도시에서 끝..
1. 문제 링크 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net 2. 문제 개요 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 3. 문제 힌트 연속된 ..
1. 문제 링크 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 문제 개요 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. i. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. ii. N번 집의 색은 N-1번 집의 색과..
백준, boj) 11726. 2xn 타일링(C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2. 문제 개요 2xn 크기의 직사각형을 1x2, 2x1타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 3. 문제 힌트 bottom up 방식으로 진행한다. 처음부터 쌓아 올릴 건데 어떤 데이터가 시작이 되어야 할까 잘 생각해보자. 4. 문제 풀기 dp[i]를 i번째 열에서의 최대 방법의 수라고 하자. 그럼 1칸을 전진하고자 하면, 세로로 길쭉한 벽돌을 쌓으면 된다. 그렇다면 i번째 칸을 쌓을..
1. 문제 링크 https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 가중치이다(1 ≤ i ≤ n). 셋째 줄부터 마지막 줄까지는 에지 리스트가 주어지는데, 한 줄에 하나의 에지를 나타낸다. 에지는 정점의 쌍으로 주어진다. 입력되는 정수들 사이에는 콤마가 없고 대신 빈칸이 하나 혹은 그 이상 있다. 가중치 www.acmicpc.net 2. 문제 개요 가중치가 가장 큰 최대 독립 집합을 찾는 것. 3. 문제 힌트 DP를 사용하자. 나를 포함하거나 ..