9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 1. 문제 설명 예제 입력 1에서 첫 번째 테스트 케이스는 문제 속 예시와 동일하고, 두 번째 테스트 케이스는 하늘색 박스를 친 스티커를 골랐을 때가 점수가 최대가 된다. 2. 구현 아이디어 처음 봤을 때 백준 1149번: RGB 거리와 비슷하게 풀면 될 것 같다는 생각이 들었다. 그래서 점화식을 아래와 같이 세웠다. 🍙 점화식 dp[0][i] = dp[1][i-1] + board[0][i] dp[1][i] = dp[0][i-1] + board[1][..

1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 1. 문제 각 예제별 트리의 모습을 입력 오른쪽에 그림으로 표현하였다. 2. 구현 아이디어 1 - 틀렸습니다 그래프를 표현하는 방법에는 인접 행렬과 인접 리스트가 있는데, 인접 리스트 방식을 사용하였다. map 자료구조를 사용하여 key는 부모 노드, value는 자식 노드의 배열로 하였다. 재귀(DFS)를 사용하여 자식 노드가 없을 때를 종료 조건으로 하고 종료 조건일 때마다 리프 노드의 개수를 +1하도록 재귀 함수를 구현하였다. 만약 제거할 노드가 루트..

2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 1. 문제 아래 그림과 같이 c로 표시된 부분은 녹아서 빈 칸이 되고, 빨간색으로 표시한 치즈의 가장자리가 새로운 'c'가 된다. 3시간 후 모든 치즈가 녹아 없어졌고, 모두 녹기 1시간 전 치즈의 개수는 에서 확인할 수 있듯 5개이다. 그렇기 때문에 첫 줄에는 3, 두 번째 줄에는 5를 출력한다. 2. 구현 아이디어 이번 문제에서는 치즈 안에 있는 구멍(위 그림 속 빨간 영역)과 치즈 밖의 공간을 어떻게 구분할지가 핵심 포인트이다. 치즈 안의 공간을 단순히 0이라고 하고 인접한 ..

2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 1. 문제 2. 구현 아이디어 자두는 최대 30번 움직이고, 1번 나무 또는 2번 나무로 이동하므로(0, 1) 전체 경우의 수는 2^30가지이다. 그렇기 때문에 완전탐색으로 푸는 것은 불가능하다. (i-1)초일 때 최대 자두 갯수를 알면, 이동할지 말지 여부에 따라 i초일 때의 최대 자두 갯수를 알 수 있기 때문에 DP로 문제를 풀 수 있다. 문제에서 3가지 상태(이동 횟수, 자두의 위치, 흐른 시간)이 있기 때문에 3차원 배열로 각 상태에 따른 자두의 최대 개수를 DP..

3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 1. 문제 예제 1을 그림으로 표현하면 다음과 같다. 개똥벌레가 높이가 3.5, 5.5, 6.5인 지점을 지날 때 파괴해야 하는 장애물이 2개로 이 때가 최소가 된다. 2. 구현 아이디어 석순과 종유석을 따로 저장한다 종유석은 (높이)-(장애물의 길이)로 저장한다 반복문을 통해 모든 지점에 대해 각 위치에 대해 파괴해야 할 장애물의 위치를 센다 편의상 0.5, 1.5처럼 X.5 지점이라고 생각하자 이분 탐색을 사용하여 나는 지점(target)의 위치를 확인하고, 그..

1. 문제 2. 구현 아이디어 - 맞았습니다!! 구역의 개수를 세면 되는 그래프 문제이다. BFS와 DFS 둘 다 가능하기 때문에 편한대로 사용하면 된다. 나는 BFS로 문제를 풀었다. 주의 ⚠️ 나는 평소에 행을 x, 열을 y로 푸는데 배추의 위치가 (열, 행) 순으로 들어오기 때문에 순서가 바뀌지 않도록 주의하여야 한다! 2중 반복문으로 배추밭 배열을 돌면서 현재 위치가 1이고 아직 방문하지 않았다면 해당 좌표를 시작점으로 BFS를 돈다. BFS를 돈 뒤, 배추흰지렁이의 개수(ret)를 +1해준다. 일반적인 BFS 문제이고, 자세한 설명은 코드에 주석으로 달겠다. #include using namespace std; int t; int m, n, k; int x, y; int arr[54][54]; ..