hotamul의 개발 이야기

url: https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 핵심 1. dfs 문제 (회귀 함수로 구현) 2. 전달 인자는 현재 날짜, 이전에 추가한 날짜, 현재 돈 총합 void dfs(int day, int post, int sum); 3. schedule 배열 생성 (상담에 걸리는 시간, 받을 수 있는 돈 정보 저장) 4. 다음과 같이 회귀 함수 구현 ... for (int i = day; i N + 1) { int m_day = day - schedule[post].t; if (m_day

url: https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 풀이 핵심 1. STL queue 활용 문제 풀이 (한 공간에 여러 개의 파이어볼 있을 수 있음) 2. 이동 시킬 때 이미 이동했던 파이어볼을 또 이동시키지 않기 위해 동일한 크기의 queue temp 배열 이용 3. 맵을 넘어갈 때는 다음 처럼 처리 for (int i = 0; i < cur.s; i++) { nr += dr[cur.d], nc +..

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/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 풀이 핵심 1. 회전 방향을 미리 저장 한다. 회전 시킬 기어와 하나 건너 맞물리는 기어는 회전 시킬 기어와 회전 방향이 같고 나머지 두 개의 기어는 방향이 회전 시킬 기어와 반대이다. 나머지 연산 이용 int cw[4]; for (int i = 0; i < 2; i++) { cw[(idx + 2 * i) % 4] = d; // idx는 회전 시킬 기어의 index이다. cw[(idx..

url: https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 핵심 1. 전형적인 시뮬레이션 / 구현 문제 2. 왼쪽 방향 탐색 (반시계 방향 회전) 을 위해 다음과 같이 나머지 연산 사용 int next = robot.dir; // 현재 방향 next에 저장 for (int i =0; i < 4; i++){ // 4 방향 탐색 next = (next + 3) % 4; // 반시계 방향 회전 ... } 3. 중복 탐색을 막기 위해 check ..

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)..

https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 풀이 핵심 1. BloodFill 문제로 BFS를 이용해 구현 2. 값이 모두 true인 flag[4] 생성, 벽으로 막힌 곳 찾기 위해 다음과 같이 구현, false로 표시 된 방향으로는 탐색 하지 않음. bool flag[4] = { 1,1,1,1 }; int tmp = map[cur.r][cur.c]; for (int i = 0; i < 4; i++) { if (tmp % 2) { fl..

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. 공기청정기의 위, 아래 순환 구..