귀염둥이의 메모

www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net BFS로 간단하게 풀 수 있는 문제이다. 비가 내리지 않는 경우를 생각하지 않아서 계속 틀렸었다. 지역의 높이를 받을 때 가장 높은 지역의 높이를 high에 저장한다. 비가 내리지 않는 경우 k = 0 부터 k = high - 1 까지 오는 경우까지 BFS를 돌려서 최대 안전영역 수를 갱신시킨다. 소스코드 #include using namespace std; int n, mx, high, result; int m[10..

www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제를 읽었을 때 많이 복잡해 보였는데 생각보다 간단하게 풀렸다. 주어진 조건 그대로 작성하였다. 북 : 0, 동 : 1, 남 : 2, 서: 3 rot 배열의 index는 현재 바라 보는 방향이고, 배열 값을 현재 좌표에 각각 더하면 왼쪽 좌표이다. ex) 북쪽(index = 0) 일 때 (x+ rot[0][0], y + rot[0][1])은 지금 북쪽을 바라봤을 때 왼쪽 좌표 (r, c) back 배열의 i..

www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 구현이 조금 까다로워서 시간이 조금 걸렸다. 공기 순환 방향인 up, down 배열을 선언했다. up : {오른쪽, 위, 왼쪽, 아래} down : {오른쪽, 아래, 왼쪽, 위} 1. 미세먼지 확산 미세먼지가 있는 좌표와 확산되기 전 먼지 값(origin)을 큐에 넣는다. 확산 가능한 곳이면 origin/5을 더하고, 확산시킨 먼지 값을 origin/5 만큼 빼준다. 2. 공기청정기 작동 청정기 (위, 아래)..

www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net BFS를 이용해서 해결할 수 있었다. +u와 -d씩 움직이며 탐색을 한다. 탈출 조건은 g(목표점)에 도달했을때 (vis배열 값 - 1) 을 return한다. vis배열은 버튼을 누른횟수가 들어가는데 처음에 0이 아닌 1이 들어가기때문에 (vis배열 값 - 1) 을 return 해준다. 탐색을 완전히 할때까지 g에 도달하지 못하면 "use the stairs"을 출력한다. 소스코드 #include using namespac..

www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 백트래킹을 활용하여 완전 탐색을 했다. 1. 현재 위치에서 4 방향(위, 아래, 왼, 오)으로 진행하며 사각형이 4개가 될 때마다 합의 최댓값을 갱신해 주었다. 2. 위 과정이 끝나고 k == 1일때 가능한 모든 ㅗ 모양에 대해서 최댓값을 갱신했다. 소스코드 #include using namespace std; int n, m, mx, s; int dx[4] = {0, 0, -1, 1}; int dy[4] = ..

www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net vis 배열에 스타트팀 인원들을 true로 표시하였고, 링크팀 인원들은 false이다. 각각의 모든 경우에 대해서 능력치 차이를 비교하여 차이의 최소를 구하였다. 소스코드 #include using namespace std; int n; int minimum = INT32_MAX; int vis[21]; int stat[21][21]; void dfs(int k, int start) { if (k == n / 2) { int st ..

www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 이차 원 배열 M에 사과는 1로 표시하고, 뱀의 몸은 -1로 표시를 하였다. int 변수 dx와 dy를 통해서 현재 진행방향을 나타 냈다. 벽 또는 자신의 몸에 부딪힐 때 종료 조건을 걸고 break 했다. 몸이 되는 부분의 차례로 큐에 넣어서 사과를 먹지 않았을 때 꼬리 부분(가장 나중에 큐에 들어간 부분)을 없앴다. 위, 아래, 오른쪽, 왼쪽 진행 방향 각각에 대해서 'L'과 'D'일 때를 처리해 주었다. -> 이..