본문 바로가기

백준323

[백준 4883] 삼각 그래프 (C++) https://www.acmicpc.net/problem/4883 문제이 문제는 삼각 그래프의 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최단 경로를 찾는 문제이다.삼각 그래프는 사이클이 없는 그래프로 N ≥ 2 개의 행과 3열로 이루어져 있다. 삼각 그래프는 보통 그래프와 다르게 간선이 아닌 정점에 비용이 있다. 어떤 경로의 비용은 그 경로에서 지나간 정점의 비용의 합이다.오른쪽 그림은 N = 4인 삼각 그래프이고, 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 경로 중 아래로만 가는 경로의 비용은 7+13+3+6 = 29가 된다. 삼각 그래프의 간선은 항상 오른쪽 그림과 같은 형태로 연결되어 있다. 입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫.. 2024. 5. 29.
[백준 1788] 피보나치 수의 확장 (C++) https://www.acmicpc.net/problem/1788 문제 𝐹(𝑛):= {0                        if 𝑛=0;            1                         if 𝑛=1;            𝐹(𝑛−1) + 𝐹(𝑛−2) if 𝑛>1.}수학에서, 피보나치 수는 위의 점화식과 같이 귀납적으로 정의되는 수열이다. 위의 식에서도 알 수 있듯이, 피보나치 수 F(n)은 0 이상의 n에 대해서만 정의된다.하지만 피보나치 수 F(n)을 n이 음수인 경우로도 확장시킬 수 있다. 위의 식에서 n > 1인 경우에만 성립하는 F(n) = F(n-1) + F(n-2)를 n ≤ 1일 때도 성립되도록 정의하는 것이다. 예를 들어 n = 1일 때 F(1) = F.. 2024. 5. 28.
[백준 2294] 동전 2 (C++) https://www.acmicpc.net/problem/2294 문제n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 입력첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. 출력첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다. 문제 풀이dp 문제.i번째 동전의 가치가 A일 때 A * x원은 만들 수 있는 금액이며, 이 때 동전의 개수는 .. 2024. 5. 27.
[백준 18352] 특정 거리의 도시 찾기 (C++) https://www.acmicpc.net/problem/18352문제어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자. 이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.입력 첫째 줄에 도시의 개수 N, 도로의 개.. 2024. 5. 26.
[백준 27724] 팝핀 소다 (C++) https://www.acmicpc.net/problem/27724문제민겸이는 shake! 2022를 맞아 레크리에이션 행사를 기획하였다. 이 행사의 메인 컨텐츠는 탄산이 매우 강력해서 마시기 힘든 팝핀 소다를 빨리 마시는 대회이다. 이 대회는 아래와 같이 진행된다.대회에는 총 𝑁(단, 𝑁은 2의 거듭제곱수)명의 선수가 참가한다. 𝑁명의 선수들은 양의 정수로 표현 가능한 탄산 내성을 가지고 있다. 각 선수의 탄산 내성은 1 이상 𝑁 이하이며, 각 선수의 탄산 내성은 중복되지 않는다. 𝑁명의 선수들은 다른 선수와 두 명씩 짝지어 빨리 마시기 대결을 한다. 이 과정에서 총 𝑁/2번의 대결이 진행된다. 각 대결의 패자 𝑁/2명은 대회에서 나가고, 승자 𝑁/2명은 동일한 방식으로 두 명씩 짝지어 .. 2024. 5. 25.
[백준 12738] 가장 긴 증가하는 부분 수열 3 (C++) https://www.acmicpc.net/problem/12738 문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) 출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 문제 풀이N이 1,000,000까지이므로 각 인덱스 i마다 인덱스 0부터 i-1까지 탐색하는 O.. 2024. 5. 24.
[백준 12847] 꿀 아르바이트 (C++) https://www.acmicpc.net/problem/12847 문제윤호는 퍼주기로 유명한 편의점 사장이다. 그의 편의점에는 특이한 임금 체계를 가지고 있다.각 날마다 일의 차이때문에 일마다 급여가 정해져 있다.윤호는 오차 없이 일급을 따박 따박 당일에 준다.정해진 일 수 만큼만 일을 시킨다.한번이라도 퇴직한 자를 다시 취직 시키지 않는다. (만약 취직을 한다면, 일을 시작 한 날부터 끝날 때까지 하루도 빠지면 안 된다.)무서운 아르바이트를 짤린 준수는 n+1일 후에 001에 월세를 내야 해서 윤호가 사장으로 있는 편의점에 취직하려 한다. 다행히 주변 퇴직자들의 얘기로 급여에 관련해 파악했다. 또한 퇴직자들의 급여 통계를 통해 당장 n일 후까지 일급 정보를 알아냈다. 하지만 준수는 시험을 준비해야 하.. 2024. 5. 23.
[백준 14931] 물수제비 (SUJEBI) (C++) https://www.acmicpc.net/problem/14931 문제급격한 기후변화로 최근 대곽나라의 많은 강에서 생태계 교란종이 나타나고 있다. 이에 대곽나라의 이기범 대통령은 국무회의를 주재해 정부 차원의 대책을 논의하게 되었다. 대통령, 국무총리, 환경부 장관은 물론 26부의 장관 및 차관이 모여 열띤 토론을 벌였다. 많은 좋은 의견이 나왔지만 그 중 단 한 계획만이 만장일치로 통과되었으니 일명 Flat Dumpling Plan (수제비 계획)으로, 강에서 돌로 물수제비를 해 여러 생태계 교란종을 맞춰 죽이는 계획이었다. 계획을 이행할 강의 강폭은 L(1 ≤ L ≤1,000,000)로 강을 L개의 연속한 칸으로 모델링할 수 있다. 환경부에서는 강의 1번 칸, 2번 칸, … L번 칸 각각에 살고 .. 2024. 5. 22.
[백준 1987] 알파벳 (C++) https://www.acmicpc.net/problem/1987 문제세로 𝑅칸, 가로 𝐶칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 입력첫째 줄에 𝑅과 𝐶가 빈칸을 사이에 두고 주어진다. (1 ≤ 𝑅,𝐶 ≤ 20) 둘째 줄부터 𝑅개의 줄에 걸쳐.. 2024. 5. 21.

티스토리툴바