본문 바로가기

알고리즘/백준93

[백준/C,C++] 7579번: 앱 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 해당 문제에서 앱의 개수는 100개 이하이고, 확보해야하는 메모리는 10,000,000바이트 이하입니다. 100 x 10,000,000 는 10억으로 너무 크기 때문에, 비활성화 했을 경우의 최대 비용인 100을 사용해 DP 점화식을 짜야합니다. DP[i]를 i의 비용이 주어졌을때 확보할 수 있는 최대 메모리라고 가정해봅시다. 5 60 30 10 20 35 40 3 0 3 5 4 의 예제로 보겠습니.. 2021. 7. 5.
[백준/C,C++] 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 풀이 생각보다 어려운 문제였습니다. 1, 2, 5원을 1번 이상 사용해 만들 수 있는 1~10원의 경우의 수는 아래 표와 같습니다. 0 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1 1 누적 1 1 1 1 1 1 1 1 1 1 1 2 0 0 1 1 2 2 3 3 4 4 5 누적 1 1 2 2 3 3 4 4 5 5 6 5 0 0 0 0 0 1 1 2 2 3 4 누적 1 .. 2021. 7. 5.
[백준/C,C++] 10942번: 팰린드롬? https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 1, 2, 1, 3, 1, 2, 1로 예를 들어보겠습니다. S = 1, E = 7일 경우 1과 1이 같고 그 중간 범위인 2, 1, 3, 1, 2가 팰린드롬이면 팰린드롬입니다. S = 2, E = 6일 경우 2와 2가 같고 그 중간 범위인 1, 3, 1이 팰린드롬이면 팰린드롬입니다. S = 3, E = 5일 경우 1과 1이 같고 그 중간 범위인 3이 팰린드롬이면 팰린드롬입니다. 수가 하나일 경우 무조건 팰린드롬이므로 S = 1, .. 2021. 7. 5.
[백준/C,C++] 1520번: 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 해당 문제를 보고 DFS, BFS문제구나 생각을 했습니다. 관건은 동적계획법을 사용해 어떻게 연산 수를 줄이는 것인가인데 다른 고수분들의 풀이를 보고 참고해 풀었습니다. DP[y][x] = 현재 지점의 좌표가 y, x일 때, 끝지점에 도달할 수 있는 경로의 개수로 가정하고 이를 사용한다면 탐색의 횟수를 줄일 수 있습니다. 예제를 통해 적용해보겠습니다. 최초 출발 지점인 50에서 10으로 갈 수 있.. 2021. 7. 4.

티스토리툴바