https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 구현, 시뮬레이션 문제다. 문제 설명 공기청정기가 존재한다. 공기 청정기는 2x1 크기로 항상 1열에 존재하고, 위 아래 행과 두 칸 이상 떨어져 있다. 각 칸에는 미세먼지가 존재하고 이는 해당 칸의 미세먼지 / 5 만큼 4방향으로 퍼진다. 해당 칸에는 퍼진 미세먼지를 제외한 양만큼 남는다. 공기청정기가 존재하거나, 칸이 없는 경우는 퍼지지 않는다. 후에 공기 청정기가 작동하면 공기청정기 중간 ..
Algorithm/Implementation
https://www.acmicpc.net/problem/3107 3107번: IPv6 첫째 줄에 올바른 IPv6 주소가 주어진다. 이 주소는 최대 39글자이다. 또한, 주소는 숫자 0-9, 알파벳 소문자 a-f, 콜론 :으로만 이루어져 있다. www.acmicpc.net 설명 문자열 구현 문제다. 32자리의 16진수를 : 단위로 4개씩 구분한다. 이 때 두 가지 규칙이 존재한다. 1. 각 그룹의 앞자리의 0의 전체 또는 일부를 생략 할 수 있다. 2. 0으로만 이루어져 있는 그룹이 있을 경우 그 중 한 개 이상 연속된 그룹을 하나 골라 콜론 2개(::)로 바꿀 수 있다. 아래 세 가지 IPv6는 동일하다. 2001:0db8:85a3:0000:0000:8a2e:0370:7334 2001:db8:85a3:..
https://www.acmicpc.net/problem/10836 10836번: 여왕벌 입력의 첫 줄에는 격자칸의 가로와 세로 크기 M(2 ≤ M ≤ 700)과 날짜 수 N(1 ≤ N ≤ 1,000,000)이 자연수로 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다. 다음 N개의 www.acmicpc.net 구현 문제다. 문제 그대로 구현하면 되는 문제라 특별히 설명할 부분은 없다. 문제에서 특이한 점이 있다면 왼쪽 위쪽 테두리의 성장 값을 줄 때 각각의 값을 주는 게 아니라 각각의 수가 연속된 개수를 준다는 점이었따. 이 부분을 어떻게 해결할 까 하다가 바로바로 값에 넣어주려 했는데 반복문은 한 번 덜 돌지라도 코드 자체가 너무 비효율적이라 일차원 배열을 생성했다. 처참하게..
https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 구현 문제다. 모든 경우의 수를 고려해서 경사로를 놓을 수 있는지 확인하면 된다. #include using namespace std; int arr[100][100]; int visit[100][100]; int main() { // 입출력 속도를 단축시키기 위함 ios::sync_with_stdio(0); cin.tie(0); int n, l, re = 0;cin >> n >> l; for (int i = 0; i ..
https://www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 누적 합과 구현 문제다. 자신보다 사이즈가 큰 공을 찾기 위해서는 정렬이 필요하다고 생각했다. 이중 반복문으로 하나하나 검사를 하면 시간초과가 날 것 이기 때문에 효율적인 방법을 찾으려 했다. 처음에는 반복문 하나에 누적합을 구하는 방법을 사용했다. for (int i = 1; i n; for (int i = 1; i > c >> s; arr[i] = { s, c, i..
https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 구현 문제다. 마법사 상어와 파이어볼과 비슷한 문제다. https://abbiddo.tistory.com/19 큐나 벡터 하나만을 사용하면 이동한 상어에 대해 또 이동을 할 수 있다는 반례가 생긴다. 상어가 어디에 위치했는지 알기 위한 벡터와 현재 위치해 있는 상어들에 대한 정보를 담은 큐를 사용했다. 상어가 동일한 곳에 도착하면 큰 상어만 남아야 하는데 이동하자마자 큐에도 넣..
