본문 바로가기

DP3

[개쉬운 풀이] 백준 10942 팰린드롬? 문제 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니 다를 말해야 한다. 예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자. S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다. S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다. S = 3, E = 3인 경우 1은 팰린드롬이다. S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다. 자연수 N개와 질문 M개가 모.. 2024. 3. 9.
[개쉬운 풀이] 백준 2293 동전1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 생각 동전 문제는 전형적인 DP문제이다. x라는 동전이 있다면 이를 이용해 k 원을 만들고 싶으면 k-x원을 만들 수 있는.. 2024. 3. 7.
[개쉬운 풀이] 백준 1915 가장 큰 정사각형 (CPP/C++) https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 생각 정사각형은 무엇인가? 모든 변의 길이가 같고 모든 각이 직각을 이루는 사각형이다. 근데 문제에 각은 90도로 고정이 된 상태이고 길이만 생각을 하면 되겠구나! 그렇다면 좌측 상단부터 우측 하단으로 이동하면서 각 위치에서 만들 수 있는 가장 큰 정사각형을 구하고 마지막에 어떤 크기가 가장 큰지 보면 되겠구나라고 생각하였다. 여기서 문제는 각 위치에서 만들 수 있는 가장 큰 정사각형을 어떻게 구하냐이다. 나의 결론은 다음과 같다. 정사각형을 이루기 위해서는 0이 존.. 2024. 3. 4.

티스토리툴바