본문 바로가기

백준339

[백준 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.
[백준 26070] 곰곰이와 학식 (C++) https://www.acmicpc.net/problem/26070문제지금 곰곰대학교 학생식당에는 시험기간에 밤을 새, 굶주려 있는 곰곰이들이 기다리고 있다.정확히는 치킨을 먹고 싶은 곰곰이가 A마리, 피자를 먹고 싶은 곰곰이가 B마리, 햄버거를 먹고 싶은 곰곰이가 C마리 있다.총총선배는 사비를 털어 곰곰이들에게 맛있는 밥을 사주려 한다!총총선배는 학생식당에서 사용할 수 있는 치킨 식권 X장, 피자 식권 Y장, 햄버거 식권 Z장을 가지고 있다. 식권 한장을 내면, 해당 음식 1인분으로 교환받을 수 있다.또, 식당에서는 치킨 식권 3장을 피자 식권 1장으로, 피자 식권 3장을 햄버거 식권 1장으로, 햄버거 식권 3장을 치킨 식권 1장으로 교환해주는 이벤트도 하고 있다.곰곰이들을 최대한 배불리 먹이고 싶은 .. 2025. 2. 22.
[백준 23300] 웹 브라우저 2 (C++) https://www.acmicpc.net/problem/23300문제우리는 웹 페이지에 접속할 때 '웹 브라우저'를 사용한다. 웹 브라우저에는 크게 뒤로 가기(Backward), 앞으로 가기(Frontward), 웹페이지 접속(Access) 기능이 있다.사용자가 웹 사이트에 접속하면 컴퓨터의 캐시(cache)공간에 웹페이지 정보가 저장된다. 그리고 뒤로 가기 또는 앞으로 가기 기능을 사용하면 캐시 공간에 저장되어 있던 페이지의 정보를 불러오게 된다. 여기에 주헌이가 개발한 웹 브라우저에는 신기한 기능이 있는데, 바로 압축(Compress)이라는 기능이다. 압축 기능은 뒤로 가기 공간에 같은 번호의 페이지가 연속해서 들어있을 때, 이를 하나로 줄일 수 있는 기능이다.각 기능의 작동방식은 각각 다음과 같다.. 2025. 2. 20.
[백준 2852] NBA 농구 (C++) https://www.acmicpc.net/problem/2852문제동혁이는 NBA 농구 경기를 즐겨 본다. 동혁이는 골이 들어갈 때 마다 골이 들어간 시간과 팀을 적는 이상한 취미를 가지고 있다.농구 경기는 정확히 48분동안 진행된다. 각 팀이 몇 분동안 이기고 있었는지 출력하는 프로그램을 작성하시오. 입력첫째 줄에 골이 들어간 횟수 N(1 출력첫째 줄에 1번 팀이 이기고 있던 시간, 둘째 줄에 2번 팀이 이기고 있던 시간을 출력한다. 시간은 입력과 같은 형식(MM:SS)으로 출력한다. 문제 풀이문자열 문제. 골을 넣어야 이전 체크포인트부터 골을 넣은 시간까지의 점유 시간을 구할 수 있다. 따라서 골을 넣은 시간마다 현재 시간 - 이전 골을 넣은 시간을 점수에 따라 두 팀 중 한 팀에 부여해주면 된다... 2025. 2. 18.

티스토리툴바