swanzzz 님의 블로그

[오늘의 문제] https://www.acmicpc.net/problem/9461[오늘의 학습 키워드]DP구현1. 문제설명 삼각형이 위 그림과 같은 모양으로 계속 추가되는 수열의 형태를 띄고 있습니다. 주어진 그림에서 삼각형의 가장 긴 변의 길이를 구하려고 하는데 그 변에 길이가 k일때 그 변에 길이가 k인 정삼각형을 추가합니다. 이런식으로 N회 반복을 수행할 때 N번째 삼각형의 변의 길이를 구하는 프로그램을 만드는 문제 입니다.[제한사항]시간 제한 1초메모리 제한 128MB1 ≤ N ≤ 1002. 접근방식 이번 문제는 굉장히 쉽게 해결할 수 있습니다. 주어진 문제에서 P(1) 부터 P(10) 까지의 변의 길이가 주어집니다. 그 길이는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 라고 합니다. 그..

[오늘의 문제]https://www.acmicpc.net/problem/9465[오늘의 학습 키워드]DP구현1. 문제설명 주어진 스티커는 낡은 스티커라 하나의 스티커를 떼면 주변에 인접한 4방향의 스티커가 찢어져 사용할 수 없다. 따라서 스티커별로 점수를 매겨서 점수의 합이 가장 높아지게끔 스티커를 뜯으려 한다. N이 주어질 때, 2 x N 크기의 스티커의 점수의 최댓값을 구하는 프로그램을 작성하는 문제입니다.[제한사항]시간 제한 1초메모리 제한 256MB1 ≤ N ≤ 100,0002. 접근방식 이번 문제를 해결하기 위해서는 점화식을 세우는 방식이 중요합니다. 스티커가 2 x N 장 주어질 때 스티커를 선택하는 방법중 최대값을 구하는 방법을 선택해야 합니다. N이 1이 주어진 경우부터 살펴 보겠습니다. ..

[오늘의 문제]https://www.acmicpc.net/problem/2133[오늘의 학습 키워드]DP구현1. 문제설명 3 x N 크기의 벽을 2x1 타일과 1x2 타일로 채우는 경우의 수를 구하는 문제 입니다. 타일의 세로 크기가 3으로 고정되어 있고 주어진 타일은 모두 2크기의 타일이므로 N이 홀수가 될 때는 타일을 제대로 채울 수 없습니다. [제한사항]시간 제한 2초메모리 제한 128MB1 ≤ N ≤ 302. 접근방식 문제를 해결하기 위해 우선 힌트를 살펴 보았습니다. 위 그림은 3 x 12 크기의 벽을 채우는 경우의 수 중 1개를 예시로 보여준 그림 입니다. 여기서 생각해 볼 수 있는 것은 1. 짝수마다 타일을 채울 수 있다. 2. 기본적으로 반복되는 기본 모양이 존재한다. 3. 규칙을 깨는 ..

[오늘의 문제]https://www.acmicpc.net/problem/1309[오늘의 학습 키워드]DP구현1. 문제설명 가로로 2칸 세로로 N칸인 동물원에 사자를 배치하는 경우의 수를 구하는 문제 입니다. 경우의 수에는 사자를 1마리, 2마리 ,,, N 마리 등 다양한 경우의 수가 존재하는데 사자를 아예 배치하지 않는 것도 경우의 수 중 하나라고 합니다.[제한사항]시간 제한 2초메모리 제한 128MB1≤ N ≤100,000 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 2. 접근방식이 문제는 점화식만 세우면 쉽게 해결할 수 있습니다. 우선 동물원 울타리가 1칸만 주어지는 경우를 살펴보죠 1칸이 주어진다면 넣을 수 잇는 경우의 수는 다음과 같습니다. 사자를 아예 넣지 않는 ..

[오늘의 문제]https://www.acmicpc.net/problem/2225[오늘의 학습 키워드]DP구현1. 문제설명 N개의 정수가 주어질 때 N개의 정수중 K개를 이용하여 합이 N이 되는 경우의 수를 구하는 문제 입니다. 예를들어 20 2 가 주어진다면 0부터 20까지의 숫자중 2개를 사용하여 20을 만드는 경우의 수를 찾는 문제입니다. 같은 숫자를 여러번 사용해도 되고 덧셈의 순서가 바뀐다면 다른 경우로 셉니다. 즉 0 + 20 과 20 + 0 은 다른 경우의 수라는 것을 의미합니다.[제한사항]시간 제한 2초메모리 제한 128MB1 ≤ N ≤ 2001 ≤ K ≤ 2002. 접근방식 이번 문제는 점화식을 세우기 위해 N과 K의 관계를 잘 살펴보아야 합니다. 위 그림에서 N이 어떤 수가 오던간에 K가..

[오늘의 문제]https://www.acmicpc.net/problem/2293[오늘의 학습 키워드]DP구현1. 문제설명 N 가지 동전이 주어지고 만드려는 동전의 합 K가 주어질 때 동전의 합 K를 만드는 경우의 수를 출력하는 문제 입니다. 주어진 동전은 여러번 사용해도 합이 K원 되면 상관없고, 주어진 동전을 사용한 개수가 동일한데 순서가 다른 경우 이 경우는 동일한 경우로 생각합니다.[제한사항]시간 제한 0.5초메모리 제한 4MB1 ≤ N ≤ 100, 1 ≤ K ≤ 10,000 동전의 가치는 100,000보다 작거나 같은 자연수이다. 2. 접근방식 지난 시간 풀었던 동전 2 문제와 굉장히 유사한 문제 입니다. 동전 2의 경우 주어진 경우의 수 중에서 더 적은 동전을 사용하는 경우를 골라 DP에 누적시..

[오늘의 문제]https://www.acmicpc.net/problem/1699[오늘의 학습 키워드]DP구현1. 문제설명 자연수 N이 주어질 때 이 N을 만들 수 있는 제곱수의 합 중 최소의 개수를 구하는 프로그램을 작성하는 문제 입니다. 예를들어 자연수 7이 주어진 경우 7을 만들 수 있는 제곱수의 합은 2^2 + 1^2 + 1^2 + 1^2 = 7 이죠 다른 방법으로는 1^2을 7번 더해주는 방법도 존재합니다. 그러나 주어진 문제에서 항의 최소개수를 구하라 하였으니 1^2 3번 2^2 1번이 올바른 정답 이겠죠 [제한사항]시간 제한 2초메모리 제한 128MB1 ≤ N ≤ 100,0002. 접근방식 우선 자연수 N의 범위가 10만입니다. 섣부르게 중첩 반복문을 사용하면 반드시 시간초과가 발생하겠죠 이번..

[오늘의 문제]https://www.acmicpc.net/problem/11052[오늘의 학습 키워드]DP, 구현1. 문제설명문제가 길어서 복잡해 보이지만 쉽게 요약하면 구매하려는 카드의 개수 N이 주어질 때 카드 가격별로 가장 비싸게 카드를 구매하는 방법을 작성하는 프로그램을 구현하는 문제 입니다. 1 5 6 7은 각 카드별 금액으로 카드 1장 구매하는데는 1원카드 2장 구매하는데는 5원카드 3장 구매하는데는 6원카드 4장 구매하는데는 7원 입니다. 각각의 금액별로 패키징 된 카드들이고 여기서 가장 카드를 비싸게 사는 방법은 2장짜리 카드를 2번 사는 경우의 수 입니다.[제한사항]시간 제한 1초메모리 제한 256MB1 ≤ N ≤ 1,0001 ≤ Pi ≤ 10,0002. 접근방식 이 문제는 N장의 카드를..

[오늘의 문제]https://www.acmicpc.net/problem/2294[오늘의 학습 키워드]DP, 구현1. 문제설명 N개의 동전으로 K원을 만들어야 하는데 동전을 최소한의 개수로 완성하는 프로그램을 작성하는 문제 입니다.[제한사항]시간 제한 1초메모리 제한 128MB1 ≤ n ≤ 100 1 ≤ k ≤ 10,000동전의 가치는 100,000보다 작거나 같은 자연수이다.2. 접근방식이번 문제는 고민을 많이 했던 문제 입니다. 예전에 한번 풀었던 문제 인데도 방법이 잘 생각나지 않았습니다. 우선 주어진 예시를 토대로 최소한의 코인을 구하는 과정을 전체 로직을 통해 생각해 보았습니다. 주어진 코인의 종류를 통해서 목표 금액이 15원을 만드는 방법을 전체 생각해 보았습니다. 1원의 경우 목표 금액 15원..

[오늘의 문제]https://www.acmicpc.net/problem/1912[오늘의 학습 키워드]DP, 구현1. 문제설명 N개의 정수로 이루어진 수열에서 연속해서 수들의 합을 구할 때 가장 큰 수를 구하는 방법을 작성하는 문제 입니다.[제한사항]시간 제한 1초메모리 제한 128MB1 ≤ n ≤ 100,000주어지는 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수2. 접근방식 이번 문제는 쉽게 생각하면 해결이 되는 문제입니다. 수들은 음수 또는 양수로 주어집니다. -1000 부터 1000 사이의 수가 주어지니 0도 주어지겠죠 수열이 주어지면 DP 테이블을 만들고 DP 테이블에 이전 값들의 합과 현재값을 비교하는 겁니다. 그 두 수중 더 큰값으로 DP 테이블을 바꿔가면 DP 테이블을 ..