프로그래밍나무

https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 여러 가지 종류의 동전을 이용해 금액 M을 만들 수 있는 모든 경우의 수를 구하는 문제입니다. dp[0] = 1; for(int i = 0 ; i < N; i++) { for(int j = coin[i]; j

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 접근방법 이 문제는 DP를 사용하였습니다. 먼저 팰린드롬은 뒤집어도 같은 것을 말합니다. 이 문제에 DP를 적용하기 위해서는 다음과 같은 생각을 해야 합니다. 1 2 1 이라는 숫자열이 있습니다. 이 문자열은 팰린드롬입니다. 이 문자열에 앞 뒤로 같은 숫자인 2를 추가해 보면 2 1 2 1 2 처럼 팰린드롬이 됩니다. 즉, 팰린드롬에 같은 숫자를 앞뒤로 추가하면 팰린드롬이 되는 겁니다. 이를 이용해 보겠습니다. 1 2 1 1 1 1, ..

https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 접근방법 이 문제에서는 이분탐색 + BFS를 이용하였습니다. 제 풀이는 다음과 같은 3단계로 구성되었습니다. 최댓값과 최솟값의 차이를 이분탐색을 이용하여 구합니다. 해당 차이를 가진 모든 경우의 수를 구합니다. 각 경우의 수마다 BFS를 통해 (1, 1)에서 (n, n)까지 이동할 수 있는지 체크합니다. 순서 배열의 수를 검사하여 전체 최댓값과 최솟값을 구합니다. 0 ~ (..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 접근방법 해당 문제에 이분탐색을 적용하여 해결하겠습니다. 이동하는 물품들의 중량을 정해놓고 가능한지 검사해나가면 중량의 최댓값을 구할 수 있습니다. 순서 각 다리의 중량 제한의 최댓값을 구한다. low = 0, high = 중량의 최댓값으로 설정 low와 high을 가지고 이분탐색 mid = (high + low) / 2 + 1 mid 중량으로 다리..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 접근 방법 해당 문제는 그리디 알고리즘을 이용해 풀 수 있습니다. 보석의 최대 가격을 구하기 위해서는 각각의 가방에 넣을 수 있는 보석 중 최대 가격을 가진 보석을 넣어야 합니다. 결국, 각 가방에 담을 수 있는 최대 무게보다 작은 보석 중에서 제일 큰 가격을 가지고 있는 보석을 선택하면 됩니다. 하지만 보석을 넣을 때는 최대 무게가 작..

www.acmicpc.net/problem/10158 10158번: 개미 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오 www.acmicpc.net 접근방법 여러 가지 방법 중에 제일 쉬운 방법은 x좌표와 y좌표를 분리해서 생각하는 것이다. x좌표와 y좌표는 증가하다가 경계면에 부딪히면 감소하고, 감소하다가 경계면에 부딪히면 증가한다. 증감을 반복하는 것을 어떻게 구현해야 할까? 먼저 시작좌표 p에서 t를 더하게 되면 경계면이 없을 때 개미가 총 움직인 거리가 나온다. testcase같이 p가 4이고 t가 8일 때 경계면이 없다면 개미의 ..

접근방법 동전을 전부 배열에 넣어놓고 하나씩 꺼내면서 전체 배열을 갱신한다. 배열을 갱신할 때 해당 동전의 크기만큼의 앞의 원소를 해당 원소에 더한다. 예를 들어, 동전의 크기가 2일 때 a[i]=a[i]+a[i-2] 왜냐하면 동전의 크기가 2이면 i=2일 때는 동전 하나로 나타낼 수 있지만 i=4일 때는 동전 두 개로 나타내야 하기 때문이다. 코드 #include using namespace std; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); int n, k; int coin[101], arr[10001] = { 0, }; cin >> n >> k; for (int i = 0; i > coin[i]; for ..