본문 바로가기

분류 전체보기380

[백준 2239] 스도쿠 (C++) https://www.acmicpc.net/problem/2239문제스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.입력9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다... 2024. 5. 31.
[프로그래머스 Level3] 거스름돈 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/12907 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제 설명Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다. 1원을 5개 사용해서 거슬러 준다. 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러.. 2024. 5. 30.
[백준 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.

티스토리툴바