본문 바로가기

백준324

[백준 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.
[백준 1051] 숫자 정사각형 (C++) https://www.acmicpc.net/problem/1051문제N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다. 입력첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다. 출력첫째 줄에 정답 정사각형의 크기를 출력한다. 문제 풀이브루트포스 문제.1*1 한 칸은  정사각형이므로 답은 적어도 1이상이다. 3중 반복문을 이용해 문제를 해결한다. 2 이상 N이하의 정사각형 크기를 정하고, 정사각형의 왼쪽 위 위치를 크기를 결정하는 반복문 안의 2중 for문으로 결정한다. 크기가 .. 2024. 6. 29.
[백준 17251] 힘 겨루기 (C++) https://www.acmicpc.net/problem/17251 문제과거 격투가로 명성을 떨치던 힘스트롱씨는 "힘 겨루기"라는 대회를 주최하여 전국에 홍보를 하였다. 모집 공고를 보고 전국 각지에서 많은 사람들이 모였는 데, 모집 공고에 '힘'이란 것에 대해 정의하지 않아 혼란이 생긴 것이다.헬스장에서 3대 500치는 근육질 아저씨부터, 유명 RPG 게임의 힘(STR) 스탯이 높은 사람까지 여러 종류의 힘을 두고 모인 것이다.힘스트롱씨는 문득 "아는 것이 힘이다"라는 유명 격언이 떠올랐다. 예선전에서 상식 퀴즈를 통해 참가자들의 힘을 수치화하였고, 이 수치를 통해 본선 참가자를 선정하기로 하였다.그렇게 총 N명의 참가자가 본선에 진출하였다. 하지만 예상과 달리, 본선은 홍팀과 청팀 두 팀으로 나누어 .. 2024. 6. 28.
[백준 29336] 월향, 비상 (C++) https://www.acmicpc.net/problem/29336문제월간 향유회(이하 월향)의 운영진들은 고민에 빠졌다. 당장 이번 달 대회에 출제할 문제가 부족하기 때문이었다. 위기의 대회를 구할 마지막 희망, 박신욱은 운영진들이 힘을 합쳐 문제를 만들 것을 제안하였다.문제를 만들기 시작한 0일 째에 운영진 𝑁명의 역량은 각각 𝐴𝑖와 같다. 월향의 운영진들은 성장하는 인재이므로 하루가 지날 때마다 역량이 1씩 늘어난다. 운영진들은 본인의 역량에 준하는 퀄리티의 문제를 만들거나, 본인의 역량만큼 기존 문제 중 하나의 퀄리티를 높일 수 있다. 문제를 만들거나 기존 문제의 퀄리티를 높이는 데에는 시간이 걸리지 않는다. 단, 한 번 대회에 기여한 운영진은 힘들어서 더 이상 대회에 기여할 수 없다.대회가.. 2024. 6. 27.

티스토리툴바