본문 바로가기

백준322

[백준 28075] 스파이 (C++) 문제스파이 민겸이는 이웃 나라와의 평화를 위해 N일간 임무를 수행한다.민겸이는 정보 수집과 감시 2가지 임무를 수행한다. 각 임무는 수족관, 시청, 학교에서 수행할 수 있다. 두 임무는 성격이 크게 다르기 때문에 하루에 한 가지 임무만 수행할 수 있으며, 수족관, 시청, 학교는 멀리 떨어져 있기 때문에 하루에 한 가지 장소에서만 임무를 수행할 수 있다. 또한, 민겸이는 반드시 하루에 최소 하나의 임무를 수행해야 한다. 다시 말해, 민겸이는 하루에 위 표의 6가지 행동 중 하나를 선택하여 할 수 있다.민겸이는 각 장소에서 각 임무를 수행할 때, 임무 완수를 위한 진척도를 얻을 수 있다. 그러나 민겸이는 스파이이기 때문에, 같은 장소에서 오래 근무하면 사람들의 눈에 띄어 얻을 수 있는 진척도가 낮아진다. 민.. 2025. 1. 7.
[백준 13265] 색칠하기 (C++) https://www.acmicpc.net/problem/13265문제어린 토니킴은 색칠공부를 좋아한다.토니킴은 먼저 여러 동그라미와 동그라미 두 개를 연결하는 직선들 만으로 그림을 그리고 (모든 동그라미들 사이에 직선이 있을 필요는 없다), 연결된 두 동그라미는 서로 색이 다르게 되도록 색을 칠하고자 한다.이 그림을 색칠하는데 필요한 최소의 색의 개수를 구하는 문제는 어렵기 때문에 토니킴은 2 가지 색상으로 색칠이 가능한지의 여부만을 알고 싶어한다.동그라미들의 번호와 동그라미들이 서로 연결된 직선에 대한 정보가 주어졌을 때, 이 동그라미들이 2 가지 색상으로 색칠이 가능한지 알아내자. 입력입력의 첫 줄에는 테스트 케이스의 개수 T 가 주어진다.그 다음 줄부터 각 테스트 케이스에 대해 동그라미의 개수 n.. 2025. 1. 6.
[백준 31860] 열심히 일하는 중 (C++) https://www.acmicpc.net/problem/31860문제 송이는 이번 학기에 할 일이 매우 많다. N$N$개의 일 중 어떤 일부터 해야 할지 고민하던 중 송이에게 좋은 아이디어가 떠올랐다! 바로 해야 할 일 각각의 중요도를 산정하고, 중요도가 높은 일부터 하는 것이다. 송이는 하루에 하나의 일만 처리할 수 있으며, 일을 처리한 후 그 일의 중요도는 M$M$만큼 감소한다. 일의 중요도가 K$K$ 이하가 되면 그 일은 완료한 것으로 간주한다. 중요도를 일별로 산정하던 중 송이는 문득 일하면서 본인이 매일 느낄 만족감이 궁금해졌다. 오늘의 만족감은 전날의 만족감을 Y$Y$, 오늘 할 일의 중요도를 P$P$라 할 때 ⌊Y/2⌋+P$\lfloor Y/2 \rfloor+P$와 같다.예를 들면 다음과 .. 2025. 1. 5.
[백준 2624] 동전 바꿔주기 (C++) https://www.acmicpc.net/problem/2624문제명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.20 = 10×2 20 = 10×1 + 5×2 20 = 10×1 + 5×1 + 1×5 20 = 5×3 + 1×5입력으로 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의.. 2025. 1. 4.
[백준 11559] Puyo Puyo (C++) https://www.acmicpc.net/problem/11559문제뿌요뿌요의 룰은 다음과 같다.필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다.뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지.. 2025. 1. 3.
[백준 1025] 제곱수 찾기 (C++) https://www.acmicpc.net/problem/1025문제N행 M열의 표 A가 있고, 표의 각 칸에는 숫자가 하나씩 적혀있다.연두는 서로 다른 1개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다. 이렇게 선택한 칸에 적힌 수를 순서대로 이어붙이면 정수를 하나 만들 수 있다.연두가 만들 수 있는 정수 중에서 가장 큰 완전 제곱수를 구해보자. 완전 제곱수란 어떤 정수를 제곱한 수이다. 입력첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지고, 공.. 2025. 1. 2.
[백준 1956] 운동 (C++) https://www.acmicpc.net/problem/1956문제V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자.당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오. 두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다. 입력첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다.. 2025. 1. 1.
[백준 27971] 강아지는 많을수록 좋다 (C++) https://www.acmicpc.net/problem/27971문제마법소녀 마도카의 고양이에 깊은 감명을 받은 마법소녀 호무라는 자신도 마법을 이용하여 강아지 N마리를 집에서 키우기로 결심했다!호무라는 한 번의 행동에서 다음 2$2$가지 마법 중 하나를 선택하여 사용한다. 가장 처음에는 호무라의 집에 강아지가 존재하지 않는다. A-생성 마법: 강아지 A$A$마리를 호무라의 집에 생성한다. B-생성 마법: 강아지 B$B$마리를 호무라의 집에 생성한다.그러나 미숙한 마법 사용은 호무라에게 추가적인 제약 사항을 주게 되었다. 만약 호무라의 방에 생성된 강아지의 수가 M개의 닫힌구간들 [L1,R1],[L2,R2],⋯,[LM,RM] 중 하나 이상에 포함되게 된다면, 그 즉시 방에 생성된 모든 강아지가 사라지게.. 2024. 12. 31.
[백준 3671] 산업 스파이의 편지 (C++) 문제안녕하세요. 저는 산업 스파이입니다. 저의 정체를 절대 다른 사람에게 말하지 말아주세요.저의 가장 최근 일은 유명한 수학 연구소의 최신 연구 결과를 훔쳐오는 것이었습니다. 저는 매우 유능한 산업 스파이이기 때문에, 연구 결과를 어렵지 않게 얻을 수 있었습니다. 하지만, 제가 올 것을 미리 알았는지 연구소에서는 연구 결과를 모두 서류 절단기에 넣어버렸습니다. 어쩔수 없이 저는 눈물을 머금고 종이 조각을 모두 훔쳐왔습니다.저를 고용한 사람은 매우 무서운 사람입니다. 또, 저는 프로이기 때문에 실수를 용납하지 않습니다. 어떻게든 이 종이를 모두 복구해가야합니다. 이 연구소의 연구 주제는 빠른 소인수 분해입니다. 제가 가진 종이 조각에는 숫자가 한 자리씩만 적혀져 있습니다. 원래 숫자가 뭐였는지를 잘 모르겠.. 2024. 12. 30.

티스토리툴바