MG

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 동전 k일때 동전의 최소 개수를 구하는 문제입니다. 저는 0원부터 k원까지 dp를 완성해서 푸는 방식으로 해결하였습니다. dp를 모두 INF로 초기화시키고 1원부터 k원까지 dp를 돌려줍니다. dp[i]를 초기화할때 동전 벡터를 전부 돌려가면서 dp[i]랑 dp[i - 동전] 을 비교해 더 작은 값을 저장합니다. 이때 i - 동전이 0 이상일때와 dp가 INF가 아닐..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 얼핏 보면 간단해 보이지만 a, b, c의 범위와 시간 제한 때문에 조금 고민이 필요한 문제입니다. 그냥 a^b 를 c로 나누게 되면 b번 반복이 있기 때문에 시간초과가 나게 됩니다. 그렇기에 분할 정복으로 O(b) 를 O(logb) 로 만들어 줍니다. 지수법칙을 적용해 보면 a^b = a^(b/2) * a^(b/2) 로 표현되기 때문에 이를 이용해 재귀를 돌려서 풀어줍니다. 그리고 계산을 하기 전에 a를 미리 c로 나눈값을 대입해 long long 범위 초과가..

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 간단한 DP 문제입니다. 배열에 각 칸의 숫자를 입력받고 dp를 long long으로 선언해줍니다. 그리고 각 칸마다 오른쪽, 아래로 점프했을때 게임 판을 넘어가지 않는다면 그 칸의 dp 만큼 점프한 칸에 더해줍니다. 마지막 칸에 도착하면 루프를 탈출해주고 출력합니다. #include #define MAX 101 using namespace std; typedef long long ll..

https://www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 처음에 고민을 많이 하다 수학으로 풀었었습니다. 우체국의 위치를 x 로 잡고 각 마을과의 거리와 인구를 곱하면 여러 절댓값으로 이루어진 그래프가 그려지고 그 그래프의 극소점이 답이 되었습니다. 하지만 알고리즘 분류에 그리디가 있는 것을 보고 다른 풀이를 참고하다 더 간단한 방법이 있다는 것을 알게 되었습니다. 아래 ..

https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 센서 정보를 입력받고 이를 오름차순으로 정렬해 줍니다. 그러면 일직선상에 센서가 나열되고 이를 집중국의 개수 K 개의 집합으로 만드는데 이 길이의 최소값을 구하는 것이 목적입니다. 이를 계산하기 위해 인접한 센서끼리의 길이를 구해 주고 이를 오름차순으로 나열해줍니다. 그리고 이를 1번째부터 n - k 번째까지 더하면 답이 됩니다. 그 이유를 아래 그림으로 설명하자면 인접한..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 2 x n 타일링 1 에 이은 시리즈 2입니다. 전 내용과 거의 비슷한데 2 x 2 타일 하나만 생겼습니다. 이에서 볼 수 있듯이 시리즈 1처럼 DP 를 활용하는 문제입니다. 아래 그림처럼 설계가 되고 프로그래밍하면 풀립니다. #include #define MAX 1001 using namespace std; int dp[MAX]; int n; int main() { ios::sync_with_stdio(0); cin.tie(..

https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net n을 입력받고 이를 sqrt(n) 까지 소수로 나눠줍니다. 나눠줄 수 num을 2부터 시작해 나눠지지 않거나 소수가 아니면 1씩 더해줍니다. 그리고 소수판정 시에도 sqrt(num) 까지 해주고 소수로 판정되면 visit 배열로 체크해 다음부턴 판정하지 않도록 합니다. 마지막에 n이 1이면 다 나누어 떨어진 것이고 1이 아니면 마지막 소수가 되니 출력해 줍니다. #include #define MAX 3200 using namespace std; bool visit[MAX] = { false }; bool isPrim..

https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 전형적인 그리디 문제입니다. 크레인과 화물을 모두 벡터에 넣고 이를 내림차순으로 정렬합니다. 그리고 크레인을 앞에서부터 가져갈 수 있는 최대한 무거운 화물을 차례대로 가져가게 합니다. 한 번 사이클 돌 때마다 ans을 1씩 더하면 풀립니다. 그리고 예외로 제일 무거운 짐을 무게 제한이 제일 큰 크레인이 못 가져갈 경우 -1을 출력해줍니다. #include #include #incl..