dp
-
BOJ) 카드 게임알고리즘/백준 2021. 3. 7. 17:30
카드 게임 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net 문제 조건 1. 왼쪽 카드만 통에 버릴 수도 있고 왼쪽과 오른쪽 카드를 둘 다 통에 버릴 수도 있다. (점수 X) 2. 오른쪽 카드에 적힌 수 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다. 3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된..
-
BOJ) 계단 수 (1562 번)알고리즘/백준 2021. 3. 7. 17:19
계단 수 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 45656, 1210123 과 같이 각 자릿 수의 차이가 1씩 나는 수를 계단 수라고 한다. 자릿 수를 의미하는 n이 주어질 때, 이러한 계단수가 몇 개 존재하는지 구하는 문제다. 이 때, 모든 계단 수는 0으로 시작하지 않는다. DP와 비트 마스크를 활용해서 푸는 문제로, 각 자릿수, 0 ~9의 수, 비트마스크를 저장할 3차원 정수형 배열 DP를 이용해서 풀었다. 우선, n = 1인 경우, 0 ~ 9는 각각 자신 수 하나를 가진다. 이를 비트마스크로 표현해주면서, n을 증가시켰다. 0인 경우에는 0으로 시작할 수 없기 때문에, 0다음에 올 수 있는 수인 1만 dp에 추가시켜..
-
BOJ) 작업 (2056 번)알고리즘/백준 2021. 3. 3. 00:45
작업 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 작업의 개수 N이 주어지고, 다음 N줄에 거쳐 각 작업의 수행 시간과 선행돼야하는 작업의 숫자가 주어진다. K작업에서 선행되는 작업은 1 ~ K-1 사이의 작업이 주어진다. 이 문제는 DP와 위상정렬로 분류되어있다. 그래서, 위상정렬로 접근하려고 했다. ArrayList에 각 선행되는 작업들을 넣어주고, 선행작업이 없는 작업들을 Queue에 넣어주어 순회했었다. 각 작업은 상관관계가 없으면 동시에 진행되니까, group을 넣어주고, depth를 함..
-
BOJ) 자두나무 (2240 번)알고리즘/백준 2021. 2. 23. 01:12
자두나무 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 처음 위치 1을 기준으로 자두나무에서 떨어지는 열매를 최대한 받을 수 있는 개수를 구하는 문제다. 자두나무는 1과 2 위치에만 있고, 1초마다 떨어지는 위치 정보가 주어진다. DP를 이용해서 이 문제를 풀었다. DP의 인덱스는 시간과 움직이는 횟수를 가진다.1초에 n번을 움직였을 때, 가장 큰 값을 저장해나간다.이동한 횟수가 짝수일 때와 홀수일 때를 나누어주었다.for문 하나에서 인덱스만 각각 구해서 돌릴 수 있겠지만, if문을 통해 w를 넘는지 확인해주어야 하..
-
BOJ) 앱 (7579 번)알고리즘/백준 2021. 2. 15. 14:45
앱 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 스마트폰 앱을 이용하는데, 사용자에게 더욱 빠른 반응을 위해 백그라운드에서 앱이 돌아간다. 하지만, 메모리는 한계가 존재하기 때문에 새로운 앱을 실행시키기 위해서 백그라운드에서 돌아가는 앱 중 일부를 종료시켜야 한다. 종료된 앱을 다음에 이용할 때 드는 비용을 최소화하는 문제다. 설명이 조금 복잡해서 여러번 틀렸지만, 문제를 제대로 이해한 뒤의 풀이 자체는 어렵지 않았다. 우선, 실행중인 앱의 정보를 저장해주었다. 현재 메모리를 얼마나 차지하는지, 종료한 뒤에 나중..
-
BOJ) 극장 좌석알고리즘/백준 2021. 2. 12. 15:52
극장 좌석 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 1 ~ N 까지 극장에 좌석이 존재한다. VIP 티켓을 가진 사람은 티켓에 적힌 번호에 딱 앉는다. 나머지 일반 티켓의 경우 좌우로 1씩 증감한 번호에 앉을 수 있다. 이 때, 좌석에 배치할 수 있는 좌석표의 경우의 수를 구하는 문제다. 문제 자체는 크게 어렵지 않았다. N =1 일 때, 1가지 경우가 존재하고, N =2 일 때, 2가지 경우 (1, 2) 와 (2,1)이 존재한다. N =3 일 때, (1,2,3), (1,3,2), (2,1,3)이 존재한다. 같은 ..