본문 바로가기

알고리즘

 (46)
[BOJ 19585] 전설(c++) https://www.acmicpc.net/problem/19585 19585번: 전설 Sogang ICPC Team에는 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다. 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수 www.acmicpc.net 문제 설명 팀명을 지을 때 색상 이름과 닉네임을 이어서 지으면 수상할 수 있다는 전설이 있다. c개의 색상과 n개의 닉네임을 입력받는다. q개의 팀명을 입력받을 때 해당하는 팀이 전설에 따라 수상할 수 있는 지 여부를 출력하면 된다. (1 Map.find(str[i]) == cur->Map.end()) { return; } else { cur = cur->Map[str[i]]; } ..
[BOJ 5670] 휴대폰 자판(c++) https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 문제 설명 여러 개의 테스트 케이스가 있고, n개의 단어를 입력받는다. 휴대폰 자판을 누르면 입력된 문자로 시작하는 문자가 하나밖에 없으면 자동 완성할 수 있다. 모든 단어들을 입력하기 위해 버튼을 눌러야 하는 최소 횟수의 평균값을 구해야 한다. (1 child[x]; } cur->end = true; } void count(string str) { node* cur = root; for (int i ..
[BOJ 1939] 중량제한(c++) https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 문제 설명 n개의 섬들에 m개의 다리가 설치되어있다. 다리에는 중량제한이 있어 옮길 수 있는 물품이 한정 되어있다. 섬a과 섬b를 잇는 다리의 중량제한 c. 어떤 섬s에서 섬e로 이동하는 데 옮길 수 있는 물품들의 중량의 최댓값을 구해라. (2 > s >> e; func(); cout
[BOJ 2871] 아름다운 단어(c++) https://www.acmicpc.net/problem/2871 2871번: 아름다운 단어 상근이는 희원이와 놀기 위해 집에서 게임을 준비해 왔다. 한 종이에 한 글자씩 쓰여 있고, 이러한 종이 N개가 한 줄로 놓여져 있다. 두 사람 각각은 이 종이를 모아서 단어를 만들려고 한다. 각 www.acmicpc.net 문제 설명 길이가 n인 문자열이 주어진다. 상근이와 희원이는 문자열에서 문자를 하나씩 가져가 문자열을 만든다. 각자가 만든 문자를 비교해 사전순으로 앞선 사람이 이기는 게임을 진행한다. 상근이는 문자열의 맨 뒤에 있는 문자를 가져가서 순서대로 문자열을 만들고, 희원이는 아무 문자나 가져갈 수 있다. 상근이가 게임을 먼저 진행할 때, 희원이가 이길 수 있는지와 만들 수 있는 가장 아름다운 단어를..
[BOJ 2873] 롤러코스터(c++) https://www.acmicpc.net/problem/2873 2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답 www.acmicpc.net 문제 설명 rxc 크기의 표에 롤러코스터를 통해 탑승자의 기쁨 수치가 입력된다. 표의 0, 0에서 출발해 n-1, n-1에 도착할 때까지 기쁨 지수의 총합이 가장 크도록 만드는 이동경로를 출력해야 한다. (2 흰 칸 으로만 이동할 수 있다. 3. 흰 칸에서 흰 칸으로 이동할 때는 짝수 번의 이동이 필요하다. 4. r과 c 모두 짝수인 경우 r*c - 1은 홀수이다. => 기쁨 지수가 가장 낮은..
[BOJ 13904] 과제(C++) https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 문제 설명 n개의 과제가 주어지고 각 과제는 마감일의 남은 날짜(d)와 가중치(w)가 있다. 하루에 과제 한 개씩만 할 수 있을 때 수행한 가중치의 합이 가장 높도록 만들어야 한다. (1 > w; v.push_back({ d, w }); } sort(v.begin(), v.end(), compare); int day = 0; for (int i = 0; i 0; j--..
[BOJ 23309] 철도공사 (C++) https://www.acmicpc.net/problem/23309 23309번: 철도 공사 첫 번째 줄에 공사를 시작하기 이전에 있는 역의 개수를 나타내는 양의 정수 $N$과 공사 횟수를 나타내는 양의 정수 $M$이 주어진다. ($1 \le N \le 500\,000$, $1 \le M \le 1\,500\,000$) 두 번째 줄에는 공사 www.acmicpc.net 문제 설명 n개의 지하철 역이 있고, m개의 명령이 있다. 각 지하철 역에는 고유 번호가 있고, 앞 뒤 역 정보가 있다. 각 4개의 명령어를 처리하는 문제이다. BN i j : 고유 번호 i를 가진 역의 다음 역의 고유 번호를 출력하고, 그 사이에 고유 번호 j인 역을 설립 BP i j : 고유 번호 i를 가진 역의 이전 역의 고유 번호를..
[BOJ 17143] 낚시왕(c++) https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 문제설명 RxC의 배열 위에 상어가 m마리 있다. 각각의 상어들은 speed, dir, size를 가지고 있고, 1초에 dir 방향으로 speed만큼 움직인다. 만약 배열 끝에 닿으면 방향을 바꾸어 움직인다. 낚시꾼의 시작 위치는 0이고, 1초에 1씩 오른쪽으로 이동한다. 1초마다 낚시꾼이 이동하고, 해당 열의 가장 가까운 상어를 잡는다.(행 인덱스가 낮은 상어) 이후 상어가 ..

티스토리툴바