DFS, BFS 문제입니다. 1은 배추가 심어져 있는 땅입니다. 배추가 심어진 땅에 지렁이를 한마리씩 두어야 하는데 인접한 땅에 배추가 심어져 있다면 한마리만 심어도 됩니다. 몇마리의 지렁이를 심어야지 찾는 문제입니다. map을 전부 검사하면서 배추가 심어져 있으면 DFS를 통해서 인접한 곳들을 모두 0으로 해주고 count를 추가 해주었고 마지막까지 검사한 후 count를 출력하여 문제를 풀었습니다. #include using namespace std; int m, n, k; int map[60][60]; int moveX[4] = { 0, 1, 0, -1 }; int moveY[4] = { 1, 0, -1, 0 }; void init() { for (int i = 0; i < 60; ++i) { fo..

DFS, BFS 문제입니다. 1은 사람이 살고 있는 집입니다. 1과 인접해있는 곳에 1이 있으면 그곳들은 하나의 단지입니다. 이 때 몇개의 단지가 있고 단지마다 몇명이 살고 있는지 찾는 문제입니다. 먼저 입력받은 숫자들이 붙어있으므로 string으로 받아서 하나씩 잘라서 배열에 넣어주었습니다. 그리고 각 위치에서 마다 DFS를 실행하여 1이면 0으로 바꿔주면서 주변이 1인곳들을 전부 검색하고 그 수만큼 group배열에 +1씩 해줍니다. 한 단지의 인원을 다 구한경우 ++c를 해주므로써 다음 단지의 배열 위치를 지정할 수 있습니다. 모든 작업이 끝난 후 배열을 솔팅해주고 출력합니다. #include #include #include #include using namespace std; int map[30][..

다이나믹 프로그래밍 문제입니다. 1*N의 미로에서 칸마다 입력되어 있는 숫자만큼 점프 할 수 있습니다. 이 때 N의 위치까지 최소 몇번으로 갈 수 있는지 찾는 문제입니다. for문을 통해 1~N까지 반복할 때 DP[i]에서 i는 위치이고, i의 위치까지 왔을 때 최소한의 횟수를 저장합니다. DP[i] == 0 일 때는 i의 위치까지 올 수 없는 경우이므로 for문을 종료해줍니다. DP[i + j]는 현재 위치에서 점프 할 수 있는 곳입니다. 현재 계산중인 횟수 +1 보다 DP[i + j]에 저장된 값이 적거나 DP[i + j]에 아직 아무것도 쓰여지지 않은 상태이면 DP[i + j] 에 DP[i] + 1을 대입해줍니다. DP[N]이 0이면 불가능 한 경우이므로 -1을 출력하고 그렇지 않으면 DP[N]을 ..

다이나믹 프로그래밍 문제입니다. 음악이 시작했을 때 볼륨을 수정해야하며, 볼륨의 크기는 0보다 작으면 안되고 M보다 크면 안됩니다. 이 때 마지막 노래를 시작했을 때 가장 크게 키울 수 있는 볼륨의 높이를 맞추는 문제입니다. DP[i][j]를 사용해 풀었습니다. i는 음량 j는 현재 가능한 볼륨과 다음 가능한 볼륨입니다. 현재 가능한 음량에서 이번 노래의 소리를 더하고 뺀것을 DP[i][1]에 넣습니다. 이와 같은 방식을 반복하여 마지막 노래를 계산한 후 DP배열에 가장 큰 i값에 값이 들어있는 i를 출력해서 문제를 풀었습니다. #include #include using namespace std; int sound[1010]; int DP[1010][2]; int main(int argc, char *a..

다이나믹 프로그래밍 문제입니다. 좌석은 한 줄로 되어있으며, 자신의 좌석에서 왼쪽, 오른쪽 좌석과 바꿔서 앉을 수 있습니다. VIP좌석은 본인의 자리에만 앉을 수 있을 때 경우의 수를 구하는 문제입니다. 각 좌석의 크기마다 경우의 수를 구해보면 1 = 1 2 = 2 3 = 3 4 = 5 5 = 8 6 = 13 .... 다음과 같습니다. 여기서 규칙을 찾아보면 피보나치 수열의 형태를 가지는 것을 알 수 있습니다. 그래서 VIP좌석이 되기 전까지 피보나치식으로 값을 쌓아주고 VIP가 되면 다시 그 일반좌석 위치부터 피보나치수열을 쌓아갑니다. 그리고 이를 모두 곱해주면 결과값이 나옵니다. #include #include using namespace std; int seat[50]; int DP[50]; int..

다이나믹 프로그래밍 문제입니다. 덧셈과 뺄셈을 이용해서 마지막 숫자를 만들어야 하며 왼쪽부터 계산을 하며 계산 과정에서 음수가 나오거나 20을 넘으면 안됩니다. 이 때 경우의 수를 구하는 문제입니다. 왼쪽부터 차례대로 +와 -에 대해서 모두 계산을 합니다. 음수가 아니고 21보다 작으면 DP[i][j]에 넣어줍니다. 이 때 i는 현재 위치이고 j는 0~20의 값을 의미합니다. 위의 예제에서 처음 8은 DP[1][8] = 1로 나타낼 수 있으며 두번 째 3은 DP[2][8+3] += DP[1][8]; DP[2][8-3] += DP[1][8]; 으로 나타낼 수 있습니다. #include #include using namespace std; int n; int arr[110]; long long int DP[..

다이나믹 프로그래밍 문제입니다. 1번칸에서 N*M번 칸으로 갈때 O표시 되어있는 칸을 들려서 최소의 길로 갈 수 있는 경우의 수를 구하는 문제입니다. 1 2 3 4 5 6 7 (8) 9 10 11 12 13 14 15 다음과 같이 8번에 체크되어 있을 때 4, 5, 11, 12번은 체크할 필요가 없습니다. O표시된 인덱스를 checkX, checkY로 했을 때 0,0~checkX,checkY와 checkX,checkY~n-1,m-1번의 길들만 0으로 입력해주어서 체킇하도록 합니다. 0,0 부터 DFS방식으로 아래와 오른쪽을 확인하고 DP의 값이 -1이면 패스하며, 1보다 높으면 그 값을 가져오고 0이면 탐색합니다. 이 방식을 통해 DP배열에 값을 저장해서 총 가능한 경우의 수를 구할 수 있습니다. #in..

다이나믹 프로그래밍 문제입니다. 피보나치에서 조금 응용된 형태입니다. 0 = 1 1 = 1 2 = 2 3 = 4 위와 같은 기본 값을 미리 입력하고 DP[i] = DP[i - 1] + DP[i - 2] + DP[i - 3] + DP[i - 4]; 다음과 같은 방식으로 문제를 해결하였습니다. #include #include using namespace std; long long int DP[10010]; int main(int argc, char *argv[]){ int ts; int checkPoint = 3; cin >> ts; memset(DP, 0, sizeof(DP)); DP[0] = 1; DP[1] = 1; DP[2] = 2; DP[3] = 4; while (ts--) { int n; cin >..