겜돌이의 개발일지

문제 백준 1937 욕심쟁이 판다 C++ 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 dp와 dfs가 섞인 재밌는 문제이다. dp 배열은 해당 칸에서 판다가 시작할 시에, 먹을 수 있는 최대 대나무를 가지고 있는 배열이다. (-1로 초기화) dfs를 돌면서 다음과 같은 과정을 거친다. 1. 어느 곳에서 시작하든, 자기 자신 칸에 있는 대나무는 먹을 수 있다. 따라서 dp 배열의 최소값은 1이다. result 값을 먼저 1로 설정한다. 2. 상하좌우 순으로, 다음값이 현재값보다 크다면 둘 중..

문제 백준 17299 오등큰수 C++ 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 오큰수 문제와 크게 다를 건 없다. 비교하는 방식만 몇번 나왔는지 횟수를 저장하고 있는 cnt 배열을 비교하는 것으로 바꿔주면 된다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 5..

문제 백준 4883 삼각 그래프 C++ 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net 풀이 기본적인 DP문제이다. 각 행은 3열이고, 조건에 따라 열까지의 최소 거리를 저장하는 배열 dp에 따라 최소 거리를 갱신해준다. dp 배열의 첫 행 첫 열에는 쓰레기값을 넣어주는데, 시작 지점이 따로 있으므로 첫행첫열에서 최소 거리를 갱신하지 못하게 하기 위함이다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27..

문제 백준 2240 자두나무 C++ 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 풀이 전형적인 dp문제이다. 1번에서 시작한다는 문구를 놓쳐서 디버깅하는데 시간이 쪼오끔 걸렸다... (2번에서도 시작할 수 있는줄 알았음) 움직이지 않는 경우에는 첫번째에 있는 경우이므로, 그 전칸에서 바로 가져오고 1번째 칸은 1번째에서 그대로 내려오거나 / 2번째 칸에서 바꾸거나 2번째 칸은 2번째에서 그대로 내려오거나 / 1번째 칸에서 바꾸거나 각각 2가지 경우가 있으므로 이를 비교하여 더 큰 값을 취하고 dp배열에 저장해두면 ..

문제 백준 10026 적록색약 C++ 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 주어진 조건에 따라 DFS나 BFS를 활용하여 그래프를 탐색해주면 된다. 색약인 경우와 색약이 아닌 경우를 color로 구분하여, 색약이 아닌 경우에는 색깔이 같을 때만 queue에 push해주고 색약인 경우에는 빨강과 초록의 구분이 없게 하여 queue에 push 한다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28..

문제 백준 11404 플로이드 C++ 풀이 전형적인 플로이드-와샬 알고리즘 문제이다. 3중 포문을 통해 모든 정점에서부터 모든 정점까지의 최소 거리를 구한다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #include #include using namespace std; const int INF = 987654321; int n, m; int dist[101][101]; int main(..

문제 백준 11725 트리의 부모 찾기 C++ 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 1이 루트기 때문에, 1에서 DFS나 BFS를 실행하면 된다. 해당 노드에 처음 방문했을 때, 그 전 노드가 부모가 된다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 #include #include #inc..

문제 백준 1647 도시 분할 계획 C++ 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 최소 스패닝 트리를 이용한다. 1. 엣지들을 가중치에 대해 오름차순으로 정렬해주고 2. 최소 스패닝 트리를 만족하도록 가중치가 낮은 n - 2개의 엣지를 연결하면 두 그룹으로 나뉘게 된다. 3. 지금까지의 가중치의 합(ans)가 정답이 된다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2..

문제 백준 13459 구슬 탈출 C++ 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 BFS를 사용한다. 방문 체크를 [빨간색 공 x좌표][빨간색 공 y좌표][파란색 공 x좌표][파란색 공 y좌표]로 4차원 배열을 이용한다. 공을 4방향(위, 아래, 왼쪽, 오른쪽)으로 굴려주면서, 방문하지 않았을 때에만 큐에 넣어주고 도착지점에 도달할 수 있을 때까지 반복한다. 그전에 이미 10번 이상 시도했다면 조건에 부합하지 않으므로 0을 출력한다. 소스 코드 1 2 3..

문제 백준 2665 미로만들기 C++ 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 풀이 두가지 방법으로 풀었다. 첫 번째 방법 1. cnt만큼 벽을 뚫을 수 있게 설정해준다. 2. BFS() 함수를 실행하여 최대 cnt만큼 벽을 뚫으면서 도착지점에 도달할 수 있는지 없는지 확인한다. 3-1. 도착할 수 있다면 true를 return 하고 현재 cnt를 출력한다. 3-2. 도착할 수 없다면 cnt를 1증가시키고 다시 BFS() 함수를 실행한다. 방문 체크를 3차원 배열로 했는데 (y좌표, x좌표, cnt :..