hotamul의 개발 이야기

url: https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이 핵심 1. Bruth Force && Back Tracking 알고리즘 문제로 보인다. (추가한 사다리 수가 3보다 크다면 더 이상 탐색할 필요 없으므로 모두 탐색 할 수 있다) 2. DFS 이용 - check(DFS) 함수 탈출 조건 현재 사용한 사다리 수가 ans 보다 크거나 같다면 return 현재 사다리의 각 번호들이 맨 밑까지 내려왔을 때 동일 한지 확인 (맞다면 정답에 ..

url: https://hotamul.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts TISTORY 나를 표현하는 블로그를 만들어보세요. www.tistory.com 풀이 핵심 1. https://na982.tistory.com/95 참고 코드 #define _CRT_SECURE_NO_WARNINGS #include int R, C, ret; int map[8][8]; struct CCTV { int type, r, c; }; CCTV cctv[8]; int cctv_size; const int rot_size[] = { 4,2,4,4,1 }; void update(int dir, CCTV cctv) { dir %= 4; if (dir..

url: https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 핵심 1. stack + queue 기능을 할 수 있는 자료 구조 구현 stack의 top 기능을 통해 현재 뱀의 머리를 알 수 있어야 한다. pop 기능은 꼬리를 잘라내야한다 (queue의 pop) 2. 방향을 변경할 때 다음과 같이 나머지 연산을 이용한다. if (DIR[time] != 0) { // 현재 시간에 방향을 변경해야 할 경우 if (DIR[time] == 'L') { // ..

url: https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 풀이 핵심 1. 상어가 벽을 만났을 때 방향 전환을 쉽게 하기 위해 dr, dc 배열과 GetReverseDir 함수를 이용한다. const int dr[] = { 0,-1,1,0,0 }; const int dc[] = { 0,0,0,1,-1 }; // 1-->Up, 2--> Down, 3-->Right, 4-->Left int GetReverseDir(int idx)..

url: https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 핵심 1. 공기청정기 행 (row) 위치 robot_r 배열에 저장 2. map 탐색 하며 미세먼지 큐에 저장 (위치 정보 r, c 와 미세먼지 양 map[r][c]를 저장) (처음에는 위치 정보만 저장했으나 미세먼지 확산이 동시에 일어난다고 생각해야 하므로 미세먼지 양도 저장해야 함) 3. bfs와 비슷하게 (추가 push가 없음) 확산 진행 4. 공기청정기의 위, 아래 순환 구..

url: https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 풀이 핵심 1. 전형적 dynamic programing 문제 2. map[1001][1001], ans[1001][1001] 생성 3. 점화식 ans[r][c] = map[r][c] + max(map[r-1][c], map[r][c-1], map[r-1][c-1]) 코드 #define _CRT_SECURE_NO_WARNINGS #include int R, C; int ma..

url: https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 풀이 핵심 1. 전형적인 시뮬레이션 문제 2. 봄에 나이가 적은 나무 순으로 양분을 먹는 것을 구현하기 위해 deque, sort 사용 (우선순위 큐 사용 시 push 할 때 마다 정렬을 하므로 사용하면 안됨) 코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std;..