귀염둥이의 메모

www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 1을 start로, 랜선 K개중에서 가장 큰 값을 end로 지정하여 이분 탐색을 진행하면 해결 가능합니다. 조건을 만족하는 mid 값을 찾았을때 break 하고 출력을 했는데, 계속 '틀렸습니다'가 떠서 당황스러웠습니다. 실패 소스코드 #include using namespace std; typedef long long ll; ll k, n, mx; ll arr[10000]; int..

www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 소스코드 #include using namespace std; int n, m; int arr[7]; int vis[7]; int result[7]; void dfs(int k, int start) { if (k == m) { for (int i = 0; i m; for (int i = 0; i > arr[i]; sort(arr, arr + n); d..

www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 백트래킹으로 모든 경우의 수를 확인했다. 선택된 연산자를 used 배열에 저장하고, 연산자를 n - 1개 선택했을 때 나열된 숫자들에 대해서 연산을 진행했다. 그리고 max와 min을 갱신했다. 소스코드 #include using namespace std; int n; int arr[12]; int used[12]; int token[4]; int mn =..

www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net DFS 또는 BFS를 이용할 수 있는데, DFS를 이용했다. 다음 과정을 계속 반복시킨다. check, vis 등 배열 및 변수 초기화 빙산의 개수를 count 한다. (cnt변수 이용) cnt값을 확인하여 2개이상인지? 아니면 0인지? (탈출 조건 확인) 2 이상이면 조건을 만족했으므로 flag = true 0이면 빙산이 다 녹았기 때문에 0을 출력해야 함. checkSide() - 각 칸마다 바닷물에 ..

www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 시뮬레이션 문제로 dfs를 이용하여 쉽게 풀 수 있다. rotateGear 함수를 구현해서 톱니 번호, 회전 방향을 인자로 받아서 톱니 회전을 수행한다. 방문 체크를 하며 주어진 조건에 맞게 dfs를 구현. 소스코드 #include using namespace std; int k, result; int gear[5][8]; int rot[100][2]; int vis[5]; void rotateGear(i..

www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 백트래킹과 BFS를 이용해서 구현했다. 백트래킹을 이용해서 벽 3개를 세우는 모든 경우의 수를 구하였다. 벽 3개가 세워지면 1) BFS를 이용해서 바이러스를 전파시킨다. 2) 바이러스 전파가 끝난 후 안전영역을 구한다. 3) 안전영역의 최대 크기를 갱신한다. 소스코드 #include using namespace std; int n, m, result; int g[8][8]; int vis[8][8]; int bfs() {..

www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 주사위를 배열 v와 h를 통해서 표현했다. 명령에 따라서 v와 h를 규칙에 맞게 적절히 업데이트하며 조건에 맞게 코드를 작성했다. 소스코드 #include using namespace std; int n, m, x, y, k; int g[20][20]; int d[5][2] = {{0, 0}, {0, 1}, {0, -1}, {-1, 0}, {1,..

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. 공기청정기 작동 청정기 (위, 아래)..