백준
-
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) 빵집 (3109 번)알고리즘/백준 2021. 2. 23. 01:18
빵집 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다. 이 경로는 겹칠 수 없고, 서로 접할 수도 없다. 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다. 이 문제에서 필요한 제약 조건들이다. 그리고 가장 중요한 힌트는 문제의 사진 첨부에 나온다..
-
BOJ) 자두나무 (2240 번)알고리즘/백준 2021. 2. 23. 01:12
자두나무 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 처음 위치 1을 기준으로 자두나무에서 떨어지는 열매를 최대한 받을 수 있는 개수를 구하는 문제다. 자두나무는 1과 2 위치에만 있고, 1초마다 떨어지는 위치 정보가 주어진다. DP를 이용해서 이 문제를 풀었다. DP의 인덱스는 시간과 움직이는 횟수를 가진다.1초에 n번을 움직였을 때, 가장 큰 값을 저장해나간다.이동한 횟수가 짝수일 때와 홀수일 때를 나누어주었다.for문 하나에서 인덱스만 각각 구해서 돌릴 수 있겠지만, if문을 통해 w를 넘는지 확인해주어야 하..
-
BOJ) 수들의 합 2 (2003 번)알고리즘/백준 2021. 2. 18. 11:48
수들의 합 2 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net N개의 수열에서 i ~ j 번 째의 값들의 합이 M이 되는 경우를 구하는 문제다. N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000) 의 조건이 주어진다. 투포인터는 슬라이딩 윈도우와 유사하지만 다른 점은 바로 탐색 구간의 길이가 정해져있지 않다는 것이다. 투포인터를 활용해서 푸는 문제인데, 익숙하지 않아서 기록에 남겨둔다. 우선, 시작점 탐색을 도와줄 left와 끝점 탐색을 도와줄 ..
-
BOJ) 가르침 (1062 번)알고리즘/백준 2021. 2. 18. 11:40
가르침 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다. 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 구하는 문제다. 단어는 모두 소문자로 주어지고, 1