swanzzz 님의 블로그

[오늘의 문제]https://www.acmicpc.net/problem/2011[오늘의 학습 키워드]DP구현1. 문제설명 A를 1, B를 2, Z를 26 이라고 암호화 하였습니다. 첫째 줄에 5000자리 이하의 암호가 주어질 경우 이 암호로 만들 수 있는 모든 경우의 수를 찾아 출력하는 프로그램을 작성하는 문제 입니다.[제한사항]시간 제한 2초메모리 제한 128MB첫째 줄에 5000자리 이하의 암호가 주어진다.정답이 매우 크니 1000000으로 나눈 나머지를 출력2. 접근방식굉장히 어려운 문제 였습니다. 문제를 풀기 위해서는 각 숫자를 자릿수의 개념으로 접근해 보아야 합니다. 예시로 25114 를 복호화 하는 과정을 거쳐 경우의 수를 찾아 보겠습니다. 우선 25114 중 한자리만 들어온 경우를 살펴보죠..

[오늘의 문제]https://www.acmicpc.net/problem/1965[오늘의 학습 키워드]DP구현1. 문제설명 일렬로 늘어선 상자에 순서대로 상자를 넣습니다. 왼쪽에 있는 상자가 오른쪽에 있는 상자들 중 하나에 들어갈 수 있는데 상자는 크기가 달라서 자신보다 크기가 큰 상자에만 들어갈 수 있습니다. 1 5 2 3 7 크기의 상자가 늘어선 경우 1 2 3 7 순서로 상자를 넣는다면 최대 4개의 상자를 넣을 수 있죠 이런 방식으로 상자의 크기가 주어질 때, 한번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 만들어야 합니다.[제한사항]시간 제한 2초메모리 제한 128MB1 ≤ N ≤ 10002. 접근방식 문제가 저번에 풀었던 가장 긴 증가하는 부분 수열 문제와 비슷합니다. 현재 상자를 기..

[오늘의 문제] 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장의 카드를..