알고리즘/백준
[백준 13397] 구간 나누기 2 C++
www.acmicpc.net/problem/13397 13397번: 구간 나누기 2 첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N) 둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수 www.acmicpc.net m개 이하의 구간을 나누어서 각 구간마다의 최댓값 최솟값을 뺀 값 중에서, 최댓값이 나올 수 있는 모든 경우의 수에서 최댓값 중에서 최솟값을 구하는 문제입니다. 구해야하는 값이 조금 복잡하다고 느낄 수 있습니다. 각 구간마다의 최댓값 최소값을 뺀 값 중에서 최댓값을 구하는건 알겠지만, 그러한 구간의 경우수가 정말 많기 때문에, 각 경우의 수마다의 최댓값 중에서 최솟값을 구하..
[백준 1756] 피자 굽기 C++
www.acmicpc.net/problem/1756 1756번: 피자 굽기 월드피자 원주 지점에서 N개의 피자 반죽을 오븐에 넣고 구우려고 한다. 그런데, 월드피자에서 만드는 피자 반죽은 지름이 제각각이다. 그런가하면, 월드피자에서 사용하는 오븐의 모양도 몹시 www.acmicpc.net 피자 굽기는 오븐에 들어갈 피자 크기를 판단하여 오븐 안에 차곡차곡 넣고, 오븐 크기에 따라, 들어갈 수 있는 피자 칸도 달라지게 됩니다. 예제 입력으로 5 6 4 3 6 2 3의 오븐 크기가 나오는데, 이부분을 좀 더 쉽게 생각하면, 5 5 4 3 3 2 2로 숫자를 바꿔서 생각할 수 있습니다. 피자 반죽 5가 5 6을 들어가던 5 5를 들어가던 들어갈 수 있는 크기는 정해져있습니다. 5 6 4에서 4부분을 통과하지 ..
[백준 2302] 극장 좌석 C++
www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 극장 좌석의 문제는 다이나믹 프로그래밍 문제로, 수열의 규칙을 찾아보면, 피보나치 수열임을 알 수 있습니다. 그 원리를 이용해서 해당 구간의 경우의 수를 곱해주는 문제입니다. 문제에서 VIP좌석이 있지만, 일단 우리는 VIP좌석을 빼고 규칙성을 찾아봅시다. VIP좌석을 빼고 규칙을 찾으면 1부터 N까지의 가능한 경우의 수는 1번째 = 1 2번째 = 2 3번째 = 3 4번째 = 5 5번째 = 8 6번째 = 13 7번째 = 2..
[백준 2533] 사회망 서비스(SNS) C++
www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 백준 사회망 서비스 문제는 트리에서 경우의 수를 구하는 다이나믹 프로그래밍 문제입니다. 서로 연결된 친구들 중에서 얼리아답터가 아닌 노드는 하나 이상의 얼리아답터와 연결되어있어야합니다. 그 때 최소 얼리 아답타를 구하는 문제입니다. 노드 1부터 시작해서 연결되어 있는 모든 노드를 DFS로 찾아가면서 경우수를 만들어주고, Return 하면서 경우의 수를 1만큼 증가 시켜준다음 누적합을 return해주시면 되..
[백준 17471] 게리맨더링 C++
www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 이 문제는 브루트포스 문제로, 모든 경우의 수를 다 시뮬레이션 돌려보고, 문제의 조건에 맞다면 경우의 수를 +1 해줍니다. 브루트포스 문제라고 생각했던 이유는 바로, N의 제한이 10밖에 안됐기 때문입니다. 조합을 구하는데 시간복잡도는 약 O(2^N)으로, 2의 10승은 1024이고, 노드가 1개 이상일 때부터 조건이 가능하니까 때문에 2^10승 * 10정도로 생각했습니다. 원리는 두 개의 집단으로 나누면 되는데, DFS 조합을 구..
[백준 2169] 로봇 조종하기 C++
www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 이 문제는 1,1에서 시작한 로봇이 N, M까지 도달하는 경로 누적 합 중 최대값을 구하는 문제 입니다. DFS로, 각 공간마다 방향 왼쪽, 아래, 오른쪽으로 나누어서 풀면 되지만, 문제 조건 중에 N, M 제한이 1,000이기 때문에, 매번 갔던 길을 또 계산한다면 시간 복잡도가 어마하게 나올 것으로 생각되었습니다. 다이나믹프로그래밍을 사용해서, 각 지점에서 출발해서 N,M에 도달할 때의 최댓값을 저..