본문 바로가기

알고리즘349

[백준 16501] 만족도 점수 (C++) https://www.acmicpc.net/problem/16501 문제테니스 동호회 회장은 매주 참가 회원들이 만족할 만 하도록 2대 2 복식 조들을 짜야 한다. 각 회원은 참여한 게임이 대등하게 펼쳐졌을 수록 만족도가 높다. 참가 회원들의 실력 점수는 0 이상 10이하의 정수로 주어진다고 가정할 때, 한 경기에 참여한 회원의 만족도 점수는 다음과 같이 표현된다.1 -  ( |상대 팀의 실력 점수 평균 - 본인 팀의 실력 점수 평균| / 10)이 점수는 최악의 경우 0, 최상의 경우 1점을 범위로 갖는다. 회장의 목표는 너무 불만족해 탈퇴하는 회원이 없도록 하는 것이다. 이를 위해 모든 회원들이 최소 1번은 참가하게 하고, 만족도 점수의 하한을 극대화 하고 싶다.2개의 테니스 코트를 쓸 수 있고, 각 .. 2024. 6. 13.
[백준 1937] 욕심쟁이 판다 (C++) https://www.acmicpc.net/problem/1937문제n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있.. 2024. 6. 12.
[백준 2992] 크면서 작은 수 (C++) https://www.acmicpc.net/problem/2992 문제정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다.수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 같다. 하지만, 123과 432는 구성이 같지 않다. 입력첫째 줄에 X가 주어진다. (1 ≤ X ≤ 999999) X는 0으로 시작하지 않는다. 출력 첫째 줄에 결과를 출력한다. 만약 그러한 숫자가 없는 경우에는 0을 출력한다. 문제 풀이백트래킹 문제.입력 받은 숫자의 배치를 섞어서 입력 받은 숫자보다 크면서 만들 수 있는 가장 작은 수를 찾아야 한다. 입력을 문자열로 받아 각 자리의 수를 배열에 저장해두고, 해당 자리의 수를 아직 .. 2024. 6. 11.
[백준 2623] 음악프로그램 (C++) https://www.acmicpc.net/problem/2623문제인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 '뮤직 KOI'에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다. 순서를 정하기 위해서는 많은 조건을 따져야 한다.그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 가수의 출연 순서를 정해오게 하였다. 보조 PD들이 가져온 것은 아래와 같다.1 4 36 2 5 42 3첫 번째 보조 PD는 1번 가수가 먼저, 다음에 4번 가수, 다음에 3번 가수가 출연하기로 순서를 정했다. 두 번째 보조 PD는 6번, 2번, 5번, 4번 순으로 자기 담당 가수들의 순서를 정했다. 한 가수를 여러 .. 2024. 6. 10.
[백준 1240] 노드사이의 거리 (C++) https://www.acmicpc.net/problem/1240문제 𝑁개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 입력첫째 줄에 노드의 개수 𝑁과 거리를 알고 싶은 노드 쌍의 개수 𝑀이 입력되고 다음 𝑁−1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 𝑀개의 노드 쌍이 한 줄에 한 쌍씩 입력된다. 출력 𝑀개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다. 제한 2 ≤ 𝑁 ≤ 1000 1 ≤ 𝑀 ≤ 1000트리 상에 연결된 두 점과 거리는 10000 이하인 자연수이다.트리 노드의 번호는 1부터 𝑁까지 자연수이며, 두 노드가 같은 번호를 갖는 경우는 없다.문제 풀이단순 그래프.. 2024. 6. 9.
[백준 21599] 아이템 배치하기 (C++) https://www.acmicpc.net/problem/21599 문제최근 싸이컴에서 제작한 게임 ‘입부 전쟁’에서는 다양한 아이템을 활용해 전쟁의 승리 확률을 높일 수 있습니다. 아이템은 한 번에 𝑁개씩 강화할 수 있습니다.강화력이 각각 𝐴1,𝐴2,⋯,𝐴𝑁개의 아이템을 강화하려고 할 때, 아이템을 강화하는 방법은 다음과 같습니다. 𝑁$개의 아이템을 적절한 순서로 원형으로 배열합니다. 𝑖$번 아이템은 자신부터 시작해, 시계 방향으로 𝐴𝑖개의 아이템을 강화시킵니다. 𝐴𝑖=0인 아이템의 경우 다른 아이템에게 아무 영향도 주지 않습니다.만약 위 규칙에 의해 여러 번 강화되는 아이템이 있다면, 실제로는 한 번만 강화됩니다.브루는 ‘입부 전쟁’ 세계 1위를 기록한 흑왕을 이기기 위해 아이템을.. 2024. 6. 8.
[백준 1414] 불우이웃돕기 (C++) https://www.acmicpc.net/problem/1414 문제다솜이는 불우이웃 돕기 활동을 하기 위해 무엇을 할지 생각했다. 마침 집에 엄청나게 많은 랜선이 있다는 것을 깨달았다. 마침 랜선이 이렇게 많이 필요 없다고 느낀 다솜이는 랜선을 지역사회에 봉사하기로 했다.다솜이의 집에는 N개의 방이 있다. 각각의 방에는 모두 한 개의 컴퓨터가 있다. 각각의 컴퓨터는 랜선으로 연결되어 있다. 어떤 컴퓨터 A와 컴퓨터 B가 있을 때, A와 B가 서로 랜선으로 연결되어 있거나, 또 다른 컴퓨터를 통해서 연결이 되어있으면 서로 통신을 할 수 있다.다솜이는 집 안에 있는 N개의 컴퓨터를 모두 서로 연결되게 하고 싶다.N개의 컴퓨터가 서로 연결되어 있는 랜선의 길이가 주어질 때, 다솜이가 기부할 수 있는 랜선의.. 2024. 6. 7.
[백준 1254] 팰린드롬 만들기 (C++) https://www.acmicpc.net/problem/1254문제동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다.동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오. 입력첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다. 출력첫째 줄에 동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력한다. 문제 풀.. 2024. 6. 6.
[백준 1701] Cubeditor (C++) https://www.acmicpc.net/problem/1701 문제Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 끝에 새로운 에디터를 만들게 되었고, 그 에디터의 이름은 Cubeditor이다.텍스트 에디터는 찾기 기능을 지원한다. 대부분의 에디터는 찾으려고 하는 문자열이 단 한 번만 나와도 찾는다. Cubelover는 이 기능은 Cubelang에 부적합하다고 생각했다. Cubelang에서 필요한 기능은 어떤 문자열 내에서 부분 문자열이 두 번 이상 나오는 문자열을 찾는 기능이다. 이때, 두 부분 문자열은 겹쳐도 된다.예를 들.. 2024. 6. 5.

티스토리툴바