본문 바로가기

백준353

[백준 32403] 전구 주기 맞추기 (C++) https://www.acmicpc.net/problem/32403문제상필이는 크리스마스트리 장식에 사용하려고 N개의 전구를 구매했다. 이 전구에 전원을 연결하면 즉시 빛나지 않고 일정한 주기로 반짝인다. 주기가 t초인 전구는 전원을 연결하고 t초, 2×t초, 3×t초, ⋯가 지난 시각에 반짝인다.상필이는 모든 전구에 전원을 연결하고 T초가 지난 시각에 모든 전구가 동시에 반짝이게 하고 싶다. 상필이는 전구에 전원을 연결하기 전에, N개의 전구 중 하나를 선택해 그 전구의 주기를 1초만큼 늘리거나 줄일 수 있다. 단, 주기를 1초보다 작아지게 할 수는 없다.전구의 주기를 조절하는 과정을 통해 모든 전구에 전원을 연결하고 T초가 지난 시각에 모든 전구가 동시에 반짝이게 하려면 이 과정을 최소 몇 번 수행해.. 2025. 3. 16.
[백준 1740] 거듭제곱 (C++) https://www.acmicpc.net/problem/1740문제3의 제곱수를 생각하자. 3의 0제곱, 3의 1제곱, 3의 2제곱, ... 은 순서대로 1, 3, 9, 27, ... 이 된다.이를 바탕으로, 한 개 이상의 서로 다른 3의 제곱수의 합으로 표현되는 수를 생각할 수 있다. 예를 들어 30은 27과 3의 합이므로, 이러한 수에 포함된다.한 개 이상의 서로 다른 3의 제곱수의 합으로 표현되는 N번째로 작은 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. N은 500,000,000,000 이하의 자연수이다. 출력첫째 줄에 한 개 이상의 서로 다른 3의 제곱수의 합으로 표현되는 N번째로 작은 수를 출력한다. 문제 풀이수학 문제. 십진수를 이진수로 변환하는 방법에서 착안하여 문제를.. 2025. 3. 14.
[백준 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.