본문 바로가기

백준351

[백준 1850] 최대공약수 (C++) https://www.acmicpc.net/problem/1850문제모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다. 입력첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 263보다 작은 자연수이다. 출력첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다. 문제 풀이유클리드 호제법을 이용한 문제. 입력은 1의 개수로 주어지지만 A와 B 모두 1로만 이루어져 있기 때문에, 입력한 수들의 최대공약수를 구해주면 된다. 예를 들어 .. 2025. 3. 12.
[백준 16567] 바이너리 왕국 (C++) https://www.acmicpc.net/problem/16567문제바이너리 왕국의 불쌍한 하인들은 매일 바이너리 길을 청소한다. 바이너리 길은 N개의 0 또는 1로 이루어진 수열이다.0은 깨끗한 칸, 1은 더러운 칸을 의미한다.그들은 "flip"이라는 기술만을 사용해서 청소를 한다. 이것은 연속된 더러운 칸을 깨끗하게 만드는 기술이다. 즉, 연속된 1을 모두 0으로 만든다.바이너리 왕국의 악덕한 왕은 매일 하인들에게 M개의 시련을 내리는 것이 취미이다. 시련에는 2가지 종류가 있는데 다음과 같다."0": 현재 길의 모든 칸을 깨끗하게 만들기 위한 "flip"의 최소 횟수를 하인들에게 크게 외치게 한다."1 i": 바이너리 길의 i번째 칸을 더럽힌다. 단, 이미 더럽혀져 있다면 아무 일도 일어나지 않는.. 2025. 3. 10.
[백준 16969] 차량 번호판 2 (C++) https://www.acmicpc.net/problem/16969문제상도시의 차량 번호판 형식이 주어졌을 때, 가능한 차량 번호판의 개수를 구해보자.번호판에 사용할 수 있는 숫자는 0, 1, 2, ..., 8, 9이다.사용할 수 있는 문자는 a, b, c, d, ..., y, z이다.차량 번호판의 형식은 최대 1,000,000글자이고, c와 d로 이루어진 문자열로 나타낼 수 있다.c는 문자가 위치하는 자리, d는 숫자가 위치하는 자리이다.같은 문자 또는 숫자가 연속해서 2번 나타나면 안 된다.예를 들어, 형식이 "cd"이면, a1, d4, h5, k4 등이 가능하다. 형식이 "dd"인 경우에 01, 10, 34, 69는 가능하지만, 00, 11, 55, 66은 같은 숫자가 2번 연속해서 불가능하다.입력.. 2025. 3. 8.
[백준 21870] 시철이가 사랑한 GCD (C++) 문제Q1. 사막에서 바늘을 찾는 방법은?A1. 대학원생을 시킨다.Q2. 신촌에서 자취방을 구하는 방법은?A2. 대학원생을 시킨다.연희동 최고의 대학원생 시철이는 오늘도 바쁘다. 그런 시철이도 이번 주말만큼은 꼭 해야 하는 일이 있었는데, 바로 자취방을 구하는 일이다!시철이는 신촌에서 가장 아름다운 자취방을 구하고 싶다. 하지만 시철이는 매우 바빴기 때문에 직접 방을 찾아다닐 수 없었다. 그래서 시철이는 인터넷에서 본 매물번호와 GCD(Greatest Common Divisor, 최대공약수)를 이용해 자취방의 아름다움을 예측하려 했다. 아름다움을 측정하는 자세한 방법은 다음과 같다.매물번호를 나타내는 정수 배열 S가 있다. (|S|=N, |S|는 S의 원소의 개수)배열 S의 원소를 왼쪽부터 ⌊|S|2⌋$\.. 2025. 3. 6.
[백준 32625] 분할 (C++) 문제크기 N의 정수 배열 A가 있다. 다음 조건을 만족하도록 배열을 연속 구간으로 분할하는 것이 가능한지 판단하시오.배열의 모든 원소가 정확히 하나의 구간에 포함된다.각 구간의 크기는 1 이상 N 미만이며, 모든 구간의 크기는 같다.각 구간에서 최솟값과 최댓값을 더한 값이 모든 구간에서 같다. 입력첫째 줄에 배열의 크기 N이 주어진다. (2 ≤ N ≤ 100000)둘째 줄에 A의 원소 A1,A2,A3,⋯,AN이 공백으로 구분되어 주어진다. (1 ≤ Ai ≤ N) 출력조건을 만족하도록 배열을 분할하는 것이 가능하다면 1을, 그렇지 않다면 0을 첫째 줄에 출력한다. 문제 풀이브루트 포스 문제. 각 구간의 크기가 동일하므로 구간은 N의 약수여야 한다. N의 약수를 모두 구한 후, 모든 구간의 합이 같은지 확인.. 2025. 3. 4.
[백준 21967] 세워라 반석 위에 (C++) https://www.acmicpc.net/problem/21967문제드높은 남산 위에 우뚝 선(중략)세워라 반석 위에선린의 터를반석: 넓고 펀펀한 큰 돌, 너럭바위어떤 수열이 반석이라는 것은, 수열의 최댓값과 최솟값의 차이가 2 이하임을 의미한다.예를 들어 1 2 3 3 1 2는 최댓값(3)과 최솟값(1)의 차이가 2이므로 반석이고, 2 6 5 4는 최댓값(6)과 최솟값(2)의 차이가 4이므로 반석이 아니다.수열이 주어지면 수열의 연속한 부분 수열(부분 문자열, substring) 중, 가장 긴 반석의 길이를 구하는 프로그램을 작성하자. 입력첫 번째 줄에 수열의 길이 N이 주어진다.두 번째 줄에는 수열 A의 원소 A1,A2,⋯,AN이 공백으로 구분되어 주어진다.출력수열 A의 연속한 부분 수열 중 가장 .. 2025. 3. 2.
[백준 13412] 서로소 쌍 (C++) https://www.acmicpc.net/problem/13412문제두 자연수 A, B의 최대공약수를 GCD(A, B)라고 할 때, A와 B가 서로소면 GCD(A, B) = 1이다. 두 자연수 A, B의 최소공배수를 LCM(A, B)라고 할 때, A와 B가 서로소면 LCM(A, B) = A x B이다.어떤 자연수 N이 서로소인 두 자연수 A, B의 최소공배수라고 할 때, A, B로 가능한 숫자 쌍은 여러 개가 있을 수 있다. 예를 들어 N = 30인 경우 30을 최소공배수로 하는 서로소인 두 자연수로 가능한 숫자 쌍은 (1, 30), (2, 15), (3, 10), (5, 6)의 4가지가 있다.자연수 N이 주어질 때 N을 최소공배수로 하는 서로소인 자연수 쌍의 개수를 출력하는 프로그램을 작성하시오. 입.. 2025. 2. 28.
[백준 30701] 돌아온 똥게임 (C++) https://www.acmicpc.net/problem/30701문제유튜브에서 똥게임 광고를 지나치게 많이 본 근호는 본인이 직접 똥게임을 설치해서 하기로 했다.처음에 근호는 D의 전투력을 가지고 시작한다. 근호 앞에는 N개의 방이 있는데, 각 방에는 몬스터 또는 장비가 있으며 i(1 ≤ i ≤ N)번째 방에 있는 몬스터 또는 장비는 전투력 Xi를 가진다.근호는 매번 아직 돌파하지 않은 방 중 어떤 방에 먼저 들어갈지 자유롭게 정할 수 있으며, 들어간 방에 있는 내용물에 따라 다음과 같이 행동한다.몬스터가 있는 경우: 근호의 전투력이 몬스터의 전투력보다 크면 몬스터를 쓰러뜨릴 수 있으며, 이후 근호의 전투력에 몬스터의 전투력이 더해진다. 근호의 전투력이 몬스터의 전투력보다 작거나 같을 경우 근호는 패배.. 2025. 2. 26.
[백준 13423] Three Dots (C++) https://www.acmicpc.net/problem/13423문제직선 위에 서로 다른 N개의 점이 찍혀 있다. 점 i의 위치는 Xi이다. N개의 점 중 3개를 골라 가장 왼쪽에 있는 점을 a, 가운데 있는 점을 b, 가장 오른쪽에 있는 점을 c라고 하자. 각각의 점의 위치는 Xa, Xb, Xc이다. 이때 점 a, b 사이의 거리와 점 b, c사이의 거리가 같으면 세 점의 간격이 같다고 한다. 즉, Xb - Xa = Xc – Xb일 때 세 점의 간격이 같다. 다음은 N = 5인 경우의 예시이다.위 예시에서 점의 위치는 각각 -4, -1, 0, 2, 4이다. 이중 -4, -1, 0위치의 세 점을 각각 a, b, c라고 하면 Xb - Xa = 3, Xc – Xb = 1로 간격이 같지 않다. 그러나 -4,.. 2025. 2. 24.

티스토리툴바