BOJ10 [BOJ][17143] 낚시왕 문제 : www.acmicpc.net/problem/17143 시뮬을 돌려봅시당. 상어의 위치를 key값, 상어 정보(크기, 방향, 속도)를 value로 하는 map을 하나 만든다. 낚시꾼은 열의 왼쪽부터 오른쪽으로 한 칸 씩 정기적으로 이동한다. 따라서 0열부터 R-1까지 이동하면서 탐색중인 열의 0행부터 C-1까지 상어들을 탐색하며 가장 위에 있는 상어 정보를 가져온다. 해당 상어를 낚시왕이 잡게 될 것이고 따라서 이 ㄴ상어의 크기를 정답에 더해준 뒤 상어 map에서 삭제한다. 낚시왕이 어떤 상어를 잡게 될지 시뮬해보았기 때문에 이제 상어들을 이동시킨다. 상어의 이동방향대로 이동시키면 되는데 문제는 속도이다. 속도의 최대값은 1000이여서 모든 상어들(RxC = 10000)을 낚시왕이 상어를 잡는 동.. 2020. 11. 15. [BOJ][16235] 나무 재테크 문제 : www.acmicpc.net/problem/16235 N x N 크기의 땅. 처음 모든 땅에는 5만큼의 양분이 들어있다. 한 칸의 땅에는 여러 개의 나무가 심어질 수 있다. M 개의 나무를 심었다. (x, y, z) = (x 좌표, y 좌표, 나이) K 년 후 살아있는 나무 개수를 구하라. 봄 : 나무가 자신 나이만큼의 양분을 먹으면 나이가 1 증가. 양분 못 먹으면 죽는다. 자신의 칸의 양분만 먹을 수 있다. 나이가 작은 순 부터 양분 섭취. 여름 : 죽은 나무가 양분(나이/2)으로 변한다. 가을 : 나무의 나이가 5의 배수일 때 인접한 8 칸에 나이가 1인 나무가 생긴다. 겨울 : A 배열만큼의 양분이 추가된다. 구현 문제. 배열은 총 3개를 사용했다. lands : 각 칸에 있는 나무의 나.. 2020. 11. 7. [BOJ][1346] 구슬 탈출 2 문제 : www.acmicpc.net/problem/13460 너비 우선 탐색(BFS)를 이용한다. 방문 여부는 빨간 공 (x, y) 파란 공 (x, y) 이용해서 4차원 배열을 만들어서 체크한다.(check 배열) 큐 안에는 (빨간 공(x, y), 파란 공(x, y), 기울인 횟수)를 저장한다. 벽 또는 탈출구가 나올 때까지 한 방향으로 공을 계속 움직인다. 파란 공이 빠져나오는 경우는 불가능한 경우이고 빨간 공만 나온 경우는 기울인 횟수를 출력하고 종료한다. 파란 공과 빨간 공이 겹치는 경우, 기울이기 전 위치를 비교해서 겹치지 않게 해준다. 만약, 아래 방향으로 움직이는 경우 기울이기 전 빨간 공이 파란 공보다 아래에 있었다면 파란 공의 위치를 1위로 옮긴다. 공들의 위치를 겹치지 않게 조정한 다음.. 2020. 11. 1. [BOJ][16236] 아기 상어 문제 : www.acmicpc.net/problem/16236 거리가 가장 가까운 먹을 수 있는 물고기를 찾되 조건에 해당하는 물고기가 여러마리라면 가장 위, 가장 왼쪽에 있는 물고기를 먹으러 간다. 가장 가까운 먹을 수 있는 물고기를 찾아야하므로 BFS(너비우선탐색)을 하는데 가장 위, 가장 왼쪽에 있는 물고기를 찾아야 하므로 큐가 아닌 우선 순위 큐를 사용했다. 우선 순위 큐에 (현재 상어 위치와 이동하고자 하는 좌표간 거리(dist), (이동하고자 하는 좌표(x, y))) 를 저장한다. 해당 큐에서 좌표간 거리가 가장 짧고, 이동하고자 하는 좌표(x, y)를 x가 작을 수록, y가 작을수록 높은 우선순위를 가진다. 우선 순위 : dist 오름차순 -> x 오름차순 -> y 오름차순 상어가 지나갈 수.. 2020. 10. 31. [BOJ][14888] 연산자 끼워넣기 문제 : www.acmicpc.net/problem/14888 N의 범위가 2~11 이다. 백트래킹으로 돌려도 될만한 시간이다. 정수집합을 앞에서부터 탐색해가면서 가능한 부호를 모두 돌려봐서 나오는 수들 중 최대값, 최소값을 구한다. pair answer; // arr : 정수형 배열 // signCnt : 부호 개수, // ind : arr 탐색 중인 인덱스 // result : 이때까지 계산한 결과값 // sign : arr[ind]에 적용할 부호. arr[ind] 앞에 들어갈 부호 void backtracking(int[] arr, int[] signCnt, int ind, int result, int sign) { // 경계값 확인 sign 부호 확인 + 인 경우: result += arr[ind.. 2020. 10. 24. [BOJ][15686] 치킨 배달 문제 : https://www.acmicpc.net/problem/15686 백트래킹으로 풀 수 있다. 도시들을 탐색하면서 집 배열, 치킨집들 배열을 만든다. 치킨집들을 선택해나가면서 집들에서 가장 가까운 치킨집의 거리들을 갱신해나간다. // dist : i번 집과 치킨집과의 최소 거리 // ind : 치킨집 인덱스, // cnt : 선택된 치킨집 개수 void backtracking(vector dist, int ind, int cnt) { // 경계값 확인 backtracking(dist, ind + 1, cnt); // ind 번째 선택하지 않고 다음 치킨집 탐색 pair chi = chickens[ind]; // ind 번째 치킨집 좌표 저장 int sum = 0; // dist 배열 합 for .. 2020. 10. 20. 이전 1 2 다음
