블로그 언저리인 무언가

문제 : 20056 마법사 상어와 파이어볼 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net N 제한이 50, K제한이 1000밖에 안되므로 그냥 구현 문제이다. 구현 시 파이어볼 합쳐졌을 때의 관리가 어려우므로 미리 나누어 놓지 말고 합쳐만 놓았다가 나중에 이동해야 할 때 방향을 정해 큐에 다시 넣어주는 것이 코드를 짜기 편하다. Code #include #define ll long long using namespace std; struct ABC{ ll R, C, M, ..

문제 : 25201 보드 뒤집기 게임 25201번: 보드 뒤집기 게임 첫 번째 줄에는 현재 격자판 상태에서의 빨간색으로 칠해진 칸의 좌표의 개수 $N$, 곰곰이가 원하는 격자판 상태에서의 빨간색으로 칠해진 칸의 좌표의 개수 $M$ 이 공백을 사이에 두고 주어진다 www.acmicpc.net 뒤집기 마법을 쓰게 되면 좌표 기준 2*2칸의 색상이 변하기 때문에 이때 결국 각 행과 열의 색상 개수는 언제나 짝수개만큼 변한다. 따라서 처음 격자판에서 행, 열의 색깔 개수를 저장하고 원하는 격자판의 상태와 비교했을때 홀, 짝이 달라진다면 불가능한 경우임을 알 수 있다. 이를 구현하기 위해 모든 좌표 입력에 대해 행, 열의 색깔 개수를 더해주고 홀-홀 이거나 짝-짝으로 입력되면 나머지 2를 했을때 0이어야 하므로 ..

문제 : 23034 조별과제 멈춰! 23034번: 조별과제 멈춰! 교수님이 시험 기간에 조별 과제를 준비하셨다...! 가톨릭대학교의 조교 아리는 N명의 학생을 2개의 조로 구성하여 과제 공지를 하려 한다. 이때, 구성된 각 조의 인원은 1명 이상이어야 한다. 각 www.acmicpc.net 조가 2개 있고 팀원 배분은 자유롭게 할 수 있으므로 최소 신장 트리를 만들어 전체 가중치 합이 최소가 되는 트리를 찾으면 된다. 이때, 과제를 전달할 때 두 조 사이에서는 연락할 필요가 없으므로 BFS를 통해 모든 팀원 사이의 비용 중 최댓값을 구해 놓은 뒤 트리의 전체 가중치 합에서 두 팀장 사이의 비용 중 최댓값을 빼고 출력하면 된다. Code #include #define ll long long using na..

문제 : 13146 같은 수로 만들기 2 13146번: 같은 수로 만들기 2 n(1 ≤ n ≤ 1,000,000)개의 자연수 A[1], A[2], A[3], …, A[n]이 있다. 이 자연수에 Add(i)라는 연산을 하면, A[i]가 1만큼 증가한다. 이때, A[i]만 증가하는 것이 아니고, A[i]의 좌우로 인접한 같은 수의 그룹이 www.acmicpc.net 단순하게 생각했을때 배열이 오름차순 or 내림차순으로 정렬되어 있다면 abs(arr[0]-arr[N-1])번만 add()연산을 실행해주면 된다. 따라서 배열에 수가 들어올 때 마다 배열을 내림차순 수열로 만들어준다고 생각하면 현재 들어온 M번째 수가 이전보다 작은수라면 냅두고 큰수라면 현재까지 저장된 수열들을 M번째 수와 같게 만들어주면 다시 내..

문제 : 10165 버스노선 10165번: 버스 노선 첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개 www.acmicpc.net 원형으로 이루어진 버스 노선들 중에서 다른 노선에 포함되어있는 노선들을 제거한 후 출력하는 문제이다. 일단 원형노선을 알아보기 쉽게 일자로 펴기 위해서 0을 지나는 노선 들 중 가장 출발점이 앞선 것 기준으로 다시 정렬을 해주고 출발점 기준으로 찾으면서 도착점이 현재 최대 도착점보다 짧은 노선들을 제거 한 후 노선들을 정렬해 출력해주면 된다. Code #include #define ll lon..

문제 : 2873 롤러코스터 2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답 www.acmicpc.net 롤러코스터가 갈 수 있는 칸이 주어지고 이를 지나면서 가장 최대의 행복값을 가지도록 경로를 구현하는 문제이다. 기본적으로 홀*홀, 짝*홀, 홀*짝 경우에서는 ㄹ자로 순회하면 모든 칸을 지날 수 있으므로 행이나 열이 홀수인 방향을 찾아 모든 칸을 지나도록 경로를 만들어 출력하면 된다. 결국 이문제의 문제는 짝*짝 상황에서 어떻게 최댓값을 찾아내냐는 것인데 어찌어찌 머리를 굴리다 보면 [짝, 홀] 칸이나 [홀, 짝] 칸 하나만 지나지..

문제 : 20041 Escaping 20041번: Escaping 첫 번째 줄에는 경찰의 수 N이 주어진다. 단, 1 ≤ N ≤ 500,000이다. 그 다음 N 개의 줄에는 각 경찰의 초기 위치의 좌표 (xi, yi)가 공백을 사이에 두고 주어진다. 다음 줄에는 도둑의 초기 위치의 좌 www.acmicpc.net 도둑의 좌표가 주어지고 경찰의 좌표가 주어졌을 때 도둑이 영원히 도망칠 수 있는지 확인하는 문제이다. 기본적인 아이디어로는 도둑이 도망치는게 가능하다고 할때 굳이 지그재그로 갈 필요없이 위, 아래, 오른쪽, 왼쪽 중에서 한방향을 정해 쭉 달리면 된다는것을 알수 있고 이를 이용해 위, 아래, 오른쪽, 왼쪽 모두에 경찰이 존재할때만 도망치는것이 불가능함을 알수있다. 여기에서 현재 경찰이 있는 점이 ..