본문 바로가기

알고리즘/백준334

[백준 2295] 세 수의 합 (C++) https://www.acmicpc.net/problem/2295문제N(5 ≤ N ≤ 1,000)개의 자연수들로 이루어진 집합 U가 있다. 이 중에서 적당히 세 수를 골랐을 때, 그 세 수의 합 d도 U안에 포함되는 경우가 있을 수 있다. 이러한 경우들 중에서, 가장 큰 d를 찾으라.예를 들어 {2, 3, 5, 10, 18}와 같은 집합이 있다고 하자. 2+3+5 = 10이 되고, 이 수는 집합에 포함된다. 하지만 3+5+10 = 18이 되고, 이 경우가 세 수의 합이 가장 커지는 경우이다. 입력첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에 차례로 U의 원소가 하나씩 주어진다. 주어진 U는 집합이 되므로 입력되는 두 수가 같아서는 안 된다. U의 원소는 200,000,000보다 작거나 같은 자연수이.. 2024. 7. 9.
[백준 28242] 수학 선생님의 고민(Hard) (C++) 문제이 문제는 수학 선생님의 고민(Easy)의 상위 문제이고, 수학 선생님의 고민(Easy)에 이 문제의 정답 코드를 제출하여 맞힐 수 있다.차형준 선생님은 여느 때와 같이 재밌는 문제를 고민하다가 다음과 같이 양의 정수 𝑛에 대한 이차식 𝑛𝑥2 + (𝑛 + 1)𝑥 − (𝑛 + 2)을 정수 범위에서 인수분해 하는 문제를 고안하게 되었다. 𝑛이 작을 때에는 쉽게 손으로 계산할 수 있었지만, 𝑛이 커짐에 따라 문제는 버거워졌다.따라서 선생님은 수학은 잘 못해도 시키는 대로 코딩은 하는 도훈이에게 문제를 맡겼다. 하지만 도훈이는 사실 ChatGPT가 알려준 코드를 복사-붙여넣기 해왔을 뿐이라 실상은 "Hello World!" 정도나 출력할 줄 안다. 그래서 도훈이는 늘 하던 대로 ChatGPT에.. 2024. 7. 8.
[백준 20002] 사과나무 (C++) https://www.acmicpc.net/problem/20002문제N × N 크기의 정사각형 모양 과수원이 있고, N × N 개의 사과나무가 1 × 1 크기의 간격으로 모든 칸에 심어져있다.농부 형곤이가 가을을 맞아 사과를 수확하려는데, 땅주인 신영이가 "너는 과수원 내에 사과나무를 K × K 의 크기의 정사각형 모양으로만 수확해 가져갈 수 있어, 이때 K는 1보다 크거나 같고 N보다 작거나 같은 정수라구! 나머지는 내가 먹을께! 하하!" 라고 통보했다.하나의 사과나무를 수확할 때, 사과를 통해 얻을 수 있는 이익과 노동비로 빠져나가는 손해가 동시에 이루어진다.그래서 형곤이는 나무의 위치를 좌표로 하여, 사과를 통해 얻은 이익과 노동비를 더한 총이익을 2차원 배열의 형태로 정리했다.악독한 땅주인 신영.. 2024. 7. 7.
[백준 2146] 다리 만들기 (C++) https://www.acmicpc.net/problem/2146문제여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 .. 2024. 7. 6.
[백준 30646] 최대 합 순서쌍의 개수 (C++) https://www.acmicpc.net/problem/30646 문제크기가 N인 배열 a가 주어진다. 배열 a의 임의의 위치를 나타내는 두 수 i, j를 골랐을 때, 아래 두 조건을 만족하면 같은 수 순서쌍 (i, j)를 만들 수 있다.1 ≤ i ≤ j ≤ Nai = aj만들어진 같은 수 순서쌍 (i, j)의 합은 ai부터 aj까지의 합 ai + ai+1 + ai+2 + … + aj-1 + aj로 정의된다. 이때 주어진 배열에서 만들 수 있는 같은 수 순서쌍의 최대 합을 찾고, 최대 합을 가지는 같은 수 순서쌍의 개수를 출력하는 프로그램을 작성하시오.입력첫 번째 배열 a의 크기 N이 주어진다.두 번째 줄에 배열 a의 원소 a1, a2, …, aN이 주어진다. 출력주어진 배열에서 만들 수 있는 같은 수.. 2024. 7. 4.
[백준 1735] 분수 합 (C++) https://www.acmicpc.net/problem/1735문제분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자.두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다. 입력첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. 출력첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다. 문제 풀이유클리드 호제법을 이용한 문제.두 분수 A/B + C/D를 계산하면 (AD+BC) / BD이다. 따라.. 2024. 7. 3.
[백준 7562] 나이트의 이동 (C++) 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다. 출력각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다. 문제 풀이bfs 기본 문제.너.. 2024. 7. 2.
[백준 23330] 거리의 합 2 (C++) https://www.acmicpc.net/problem/23330문제수직선에 n개의 점이 찍혀 있다. 각각의 점의 x좌표가 주어졌을 때, n2개의 모든 쌍에 대해서 거리를 더한 값을 구하는 프로그램을 작성하시오.즉, 모든 i, j에 대해서 |x[i] - x[j]|의 합을 구하는 것이다.입력 첫째 줄에 n(1 ≤ n ≤ 500,000)이 주어진다. 다음 줄에는 x[1], x[2], x[3], …, x[n]이 주어진다. 각각은 0 이상 10,000,000 이하의 정수이다. 출력첫째 줄에 답을 출력한다. 문제 풀이정렬 문제.오름차순 정렬한 후 첫번째 원소에 대해 다른 모든 원소와의 거리의 합을 구한다. 이를 prevSums라고 하자. 나머지 원소는 이전 원소와의 거리의 합인 prevSums와 각 원소의 위치.. 2024. 7. 1.
[백준 9342] 염색체 (C++) https://www.acmicpc.net/problem/9342문제상근이는 생명과학 연구소에서 염색체가 특정한 패턴인지를 확인하는 일을 하고 있다. 염색체는 알파벳 대문자 (A, B, C, ..., Z)로만 이루어진 문자열이다. 상근이는 각 염색체가 다음과 같은 규칙을 만족하는지 검사해야 한다.문자열은 {A, B, C, D, E, F} 중 0개 또는 1개로 시작해야 한다.그 다음에는 A가 하나 또는 그 이상 있어야 한다.그 다음에는 F가 하나 또는 그 이상 있어야 한다.그 다음에는 C가 하나 또는 그 이상 있어야 한다.그 다음에는 {A, B, C, D, E, F} 중 0개 또는 1개가 있으며, 더 이상의 문자는 없어야 한다.문자열이 주어졌을 때, 위의 규칙을 만족하는지 구하는 프로그램을 작성하시오. 입.. 2024. 6. 30.

티스토리툴바