블로그 언저리인 무언가

문제 : 17085 십자가 2개 놓기 17085번: 십자가 2개 놓기 첫째 줄에 격자판의 크기 N, M (2 ≤ N, M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다. 항상 두 개의 십자가를 놓을 수 있는 경우만 입력으로 주어진다. www.acmicpc.net N, M의 크기가 15밖에 안되므로 단순한 구현 문제이다. 모든 칸에 대해서 십자가 크기별로 넣어봐야 하는데 총 2개의 십자가를 배치해야 하므로 재귀 함수를 이용하면 코드의 길이를 단축해서 짤 수 있다. Code #include #define ll long long using namespace std; ll N, M, ans; ll dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; string arr..

문제 : 1022 소용돌이 예쁘게 출력하기 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net [0,0], [1,1], [2,2].. 는 1, 9, 25...로 제곱수로 나타나기 때문에 [x, x]=(x*2+1)^2를 이용해 기준점으로 잡고 구현해나가면 된다. 좌표 중 절댓값이 큰 것을 기준으로 x번째 껍질에 들어가게 되는데 이때 어느 변에 있냐에 따라서 네 꼭짓점을 기준으로 더해주거나 빼면 시뮬레이션 작업 없이도 구현할 수 있다. 이후 가장 큰 값을 기준으로 setw() 함수를 이용해 공백을 출력해주면 된다. Code #include #define ll long long using namespace std; ll r1, r2, c..

문제 : 14948 군대탈출하기 14948번: 군대탈출하기 첫 줄에 각 병영의 세로 길이 n, 가로 길이 m 이 주어진다. (1 ≤ n, m ≤ 100) 다음 줄부터 차례대로 병영의 블록별 레벨 제한 k가 주어진다. (0 ≤ k ≤ 109). www.acmicpc.net 현재 기준에서 레벨 제한을 높이지 않는 것 먼저 계속 탐색하면 되므로 가중치를 레벨에 두어서 우선순위 큐에 넣고 다익스트라처럼 탐색하면 된다. 이때, 도중에 점프를 할 수 있으므로 visited배열을 3차원으로 짜서 건너뛴 적이 없다면 한번 할 수 있게 하고 도착 칸에 도달한 값 중 작은 것을 찾아 출력하면 된다. Code #include #define ll long long #define INF 1e9+7 using namespace ..

문제 : 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번째 수와 같게 만들어주면 다시 내..