devlog

출처 : https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 방법 가로로도 세로로도 붙어 있으면 안되기 때문에 경우의 수를 3가지로 나누었다. dp_l[i] = i 번째 줄에 왼쪽에 사자가 있고 오른엔 사자가 없는 경우 dp_r[i] = i 번째 줄에 오른쪽에 사자가 있고 왼쪽엔 사자가 없는 경우 dp_z[i] = i 번째 줄에 왼쪽 오른쪽 둘다 사자가 없는 경우 점화식 은 dp_l[i] = dp_z[i] + dp_r[i]; dp_r[i] = dp_z[i] + dp_l[i]; dp_z[i] = dp_z[i] + dp_l[i] + dp_r[i] 로 포현하면 가로로 세로로 붙어 ..

출처 : 3184번: 양 (acmicpc.net) 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 풀이 방법 조건 몇 가지만 추가해서 bfs로 풀이할 수 있다. board전체를 for 문을 통해 돌며 #이 아니며 방문한 적이 없다면 bfs를 호출 한다. board[y][x]가 양이면 sheep변수에 +1 board[y][x]가 늑대이면 wolf변수에 +1을 해주고 bfs가 종료되기 전에 sheep의 변수 값이 큰지 wolf의 변수 값이 큰지 비교해서 sheep이 크면 n_sheep(전체 양이 몇 ..

출처 : https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 풀이 방법 동적 계획법으로 재귀 함수를 사용해 해결했다. 재귀 함수의 기저 조건으로 1. y, x 좌표가 모두 0이면 return board[0][0] 2. y, x 좌표가 범위를 넘어가면 return 0 을 해서 선택되지 않도록 설정 3. dp[y][x] 가 -1 이 아닌 다른 값으로 설정되어 있으면 그 값을 리턴 3가지를 설정 했다. 위 3가지가 아닌 경우 재귀 함수를 ..

출처 : 1926번: 그림 (acmicpc.net) 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 방법 bfs 문제로 맵 전체를 for 문을 돌며 board[y][x] 가 1이고 visited[y][x]가 -1 인 점을 bfs(y, x)를 호출하여 그 점과 연결된 점들을 방문하여 넓이를 구하고 가장 큰 곳이면 답을 변수 ans에 저장한다. 그리고 bfs가 호출 될 때마다 그림의 개수 카운터를 증가시킨 후 출력한다. #include using namespace std; int n, m, ans = 0, cnt..

출처 : 2293번: 동전 1 (acmicpc.net) 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 방법 dp를 활용해서 풀이하는 문제이다. 0에서 n번째 까지 동전이 있는데 이중 for 문을 돌며 0번째 동전만 사용했을 때부터 n번째 동전까지 다 사용한 경우까지 더하면 된다. for (int i = 1;i n >> k; for (int i = 1;i > c[i]; } memset(dp, 0, sizeof(dp)); dp[0] = 1; //0원을 만드는 경우의 수는 1이라고 하자 for (int i =..

풀이 방법 반복된 계산을 줄여 풀이하는 dp 문제이다 stairs배열에는 계단의 점수를 저장하였다. (0인덱스에는 시작점) dp배열은 dp[i] == i번째 계단까지 오는 최대 점수이다 (i 계단을 밞고 있어야 한다) dp[1]은 당연히 stairs[1]이고 dp[2]는 stairs[1] + stairs[2]보다 큰 경우는 없으므로 stairs[1] + stairs[2]가 된다. 그럼 dp[3]은 stairs[1] + stairs[3] 또는 stairs[2] + stairs[3]가 될 수 있다. 그럼 dp[n]인 경우 점화식은 dp[n-3] + stairs[n-1] + stairs[n] (n-3을 밞고 있는 경우 중 최대 + n-2계단 뛰어넘고 n-1, n-2 계단 연속으로 밞기) 또는 dp[n-2] +..

출처 : 9663번: N-Queen (acmicpc.net) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 방법 퀸끼리는 같은 행, 열, 대각선에 놓일 수 없다. 위의 세 가지 조건중 하나(행)를 기준으로 잡고 퀸의 위치를 저장하였다. (같은 행에는 2개의 퀸이 놓일 수 없기에 한 행에는 무조건 1개의 퀸만 배치) 그래서 배열 queen_col [i]는 i번째 row에 퀸이 몇 번째 col에 있는지를 뜻한다. 백트레킹을 통해 문제를 해결해 준다. can함수를 통해 퀸을 배치할 수 있는지 확인해 준다. 같은 col인지는..

출처 : 11404번: 플로이드 (acmicpc.net) 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 방법 플로이드 와샬 알고리즘을 사용하면 된다. #include using namespace std; int INF = 987654321; int n, m, s, e, w; int edge[101][101]; void floyd() { for (int i = 1;i > m; for (int i = 1;i s >> e >> w; if (edge[s][e] > w) { edge[s][e] = w; } } f..

출처 : 2146번: 다리 만들기 (acmicpc.net) 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 방법 일단 각각의 섬들을 구분하기 위해 섬에 번호를 붙여 bfs를 통해 land배열에 넣어 주었다. 거리를 구할 때 중복된 경우를 처리하지 않기 위해 섬의 고유 넘버가 작은 쪽에서 큰 쪽으로 가는 경우만 처리했다. (큰 쪽에서 작은 쪽으로 가는 길과 작은 쪽에서 큰 쪽으로 가는 길이 똑같기 때문) for문을 통해 맵 전체를 돌며(완전 탐색) s_bfs함수를 통해 bfs를 해주는데 이때 만약 다음 칸이 0..

출처 : 2573번: 빙산 (acmicpc.net) 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 방법 일단 몇 덩어리(변수 cnt) 인지 판단 후 0이면 두 덩어리 이상 안 되는 케이스 이므로 0을 출력한 후 종료 두 덩어리 이상이면 year(기간)을 출력한 후 종료하면 된다. 만약 아직 한 덩어리 라면 빙하를 녹여주는 작업이 필요하다 빙하는 동시에 녹는데 한 덩어리씩 녹여주는 작업을 한다면 먼저 녹인 빙하가 다른 빙하에 영향을 줄 수 있기 때문에 (ex 빙하가 녹아 0이 되면 이 빙하랑 인접해..