전체 글

[백준] 부분합

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 우선 문제부터 간단하게 요약하면, 길이 N의 수열이 주어질 때, 이 수열에서 연속된 수들의 부분합 중 그 합이 S 이상이 되는 것중 가장 짧은 것의 길이를 출력해야 하는 문제입니다. 어렵지 않은 투포인터와 누적합을 이용하는 문제입니다. 실제 구현은 아래와 같습니다. 주의 해야 하는 점은 만약 합을 만들지 못하는 경우 0 을 출력해야 한다는 점만 주의해서 코드를 구성하면 됩니다. #i..

[백준] 도시 분할 계획

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 우선 문제부터 간단하게 요약하면, N개의 마을과 그 마을들을 연결하는 M개의 길이 있을 때, 마을을 두 그룹으로 나누고, 그 안에서 필요하지 않은 길을 모두 없앨 때, 길의 유지비 합을 최소로 할 때의 유지비를 구해야 하는 문제입니다. 문제를 직접 한번 읽어보는 것이 정확합니다. 우선 문제를 읽자마자 최소 신장 트리가 생각이 납니다. 그러면 최소 신장트리를 구..

[백준] 소수의 연속합

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 우선 문제부터 간단하게 요약하면, N이 주어지면, 연속된 소수의 합으로 N을 구성할 수 있는 경우의 수를 구해야 하는 문제입니다. 우선 N까지의 숫자들중 소수를 에라토스테네스의 체로 구합니다. 그리고 이 소수들을 이용하여 누적합 배열을 만들어 두고, 총 몇개의 조합이 가능한지 투포인터 알고리즘을 이용하여 탐색하면 됩니다. 실제 구현은 아래와 같습니다. #include #include #include #define MAX 4000000 using namespace std; int N; int isPrime[MAX+10..

[백준] 계단 수

https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 우선 문제부터 간단하게 요약하면, 45656과 같이 이웃한 자릿수가 모두 1차이나는 숫자들을 계단수라고 정의를 합니다. 이 때, 길이가 N 이면서 0~9까지의 숫자가 모두 등장하는 계단수가 총 몇개 있는지를 구해야 하는 문제입니다. 우선 가장 처음 생각 해볼 부분은, 12123... 12323... 위의 두가지 경우에 대해 뒤에 진행되는 부분에 대한 계산은 단 한번만 하면 된다는 점입니다. 즉 현재까지 사용된 숫자의 종류가 같고, 종료되었을 때의 가장 마지막 숫자가 같은 경우는 같은 case로 취급하면 된다는 것입니다...

[백준] 부분수열의 합 2

https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 우선 문제부터 간단하게 요약하면, N개의 정수로 이루어진 수열에서 크기가 양수인 부분수열 중, 수열의 원소를 다 더한게 S가 되는 경우의 수를 구해야 하는 문제입니다. 부분수열의 정의는 인터넷을 한번 검색하고 시작하는 것이 좋을 것 같습니다. 우선 간단하게 시간복잡도를 생각해보면, 최대 40개의 숫자가 나올 수 있으므로 해당 숫자들을 뽑거나 뽑지 않는 가짓수..

[백준] 2진수 8진수

https://www.acmicpc.net/problem/1373 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net 우선 문제부터 요약하면, 2진수가 주어지면, 해당 수를 8진수로 바꾸어서 출력해야 하는 문제입니다. 뒤에서 부터 parsing을 해야하므로 나중에 들어온 input부터 처리할 수 있는 stack등의 자료 구조를 활용할 수 있습니다. 하지만 stack을 사용하면, push는 그냥 input으로 char array를 만들어 넣을 수 있지만 pop을 하게 되면, function call이 일어나거나 하면 속도가 느려질 수 있습니다. 그래서 직접 index를 이용하여 forloop를 이용하여 처리하였습니다...

[백준] 보석 도둑

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 우선 문제부터 간단하게 요약하면, 보석점을 상덕이가 털려고 하는데, 상덕이가 가진 가방에는 각각 보석 1개씩만을 넣을 수 있고, 각각의 가방은 담을 수 있는 보석의 최대 무게를 가지고 있습니다. 이 때, 훔쳐갈 수 있는 보석의 최대 가격을 구하는 것이 문제입니다. 우선 어떤 가방이 좋은 가방일지 생각을 해보면, 당연히 무게를 많이 담을 ..

[백준] 두 배열의 합

https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 우선 문제부터 간단하게 요약하면, A={1, 3, 1, 2}, B={1, 3, 2}, T = 5 이렇게 A, B 배열과 T값이 주어질 때, A의 부배열과 B의 부배열의 합이 T가 되도록 하는 모든 경우의 수의 갯수를 구해야 합니다. 부 배열과 같은 부분에 대한 정의는 문제를 한번 직접 읽어보는 것을 추천합니다. 사실 ..