귀염둥이의 메모

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'일 때를 처리해 주었다. -> 이..