반응형 알고리즘63 백준 #1026 보물 이번 문제는 문제가 의도하는 뜻만 잘 이해하면 풀 수 있는 문제입니다. 그래서인지 정답자가 상당히 높습니다. 오늘 날짜의 정답자가 8,888명, 정답률 61.5%입니다. 숫자가 8이 연속 4개라서 캡처를 해두었습니다. 문제는 두개의 수열 A[*], B[*]이 주어졌을 때, 적절하게 A[*] 수열을 재배치 해서 다음의 식을 최소화하도록 하는 것입니다. \[ \sum_{k} A[k] \cdot B[k] \] 문제에서는 B[*] 배열은 재배열하면 안된다고 합니다. (함정입니다.) 문제는 아래 링크에 있습니다. https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로.. 2019. 12. 25. 백준 #1024 수열의 합 수열의 합은 수열이 어떻게 이루어졌느냐에 따라서 계산됩니다. 대표적으로 등차수열과 등비수열은 공식에 의해서 구할 수 있습니다. 이 문제는 연속된 수열의 합을 구하는 것이기 때문에 등차수열의 합을 이용하면 됩니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/1024 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 길이가 짝수일 때와 홀수일 때의 합이 서로 다릅니다. 초기항 s이고 길이가 n인 수열의 합은 다음과 같이 나타낼 수 있습니다. \[ s + (s+1) + ... + (s+(n-1)) = \fr.. 2019. 12. 25. 백준 #1019 책 페이지 한지민은 책을 좋아해서 도서관에서 근무한다. 그녀는 봄의 어느날 밤 책을 읽다가 문득 자신이 넘긴 책장에 있는 페이지에 얼마나 많은 숫자가 적혀있는지 궁금해졌다. 책의 페이지는 1 페이지부터 N 페이지까지 있다. 그녀가 읽은 책에는 과연 숫자가 몇개나 페이지에 적혀있는지 계산해보자. 원래 문제와는 조금 다르지만, 문득 한지민씨가 출연한 봄밤과 문제에 있는 지민이라는 이름이 겹쳐서 문제 내용을 바꾸어 보았습니다. 원래 문제는 아래의 링크에 있습니다. 난이도는 Gold I 문제입니다. https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 출력한다. www.acmicpc.ne.. 2019. 12. 25. #1017 소수쌍(네트워크 플로우) 처음 이 문제를 접했을 때에는 '혹시 쌍둥이 소수' 문제일까 하고 봤었네요. 소수쌍이 아니라 합이 소수가 되는 숫자들의 합 이야기입니다. 짝수인 N개가 주어지면, 합이 소수가 되는 쌍으로 모두 묶을 수 있다면, 첫번째 수와 묶일 수 있는 수들의 리스트를 내는 문제입니다. 난이도는 Platinum III이지만, 난이도보다는 쉬운 문제입니다. 물론 네트워크 플로우 알고리즘을 알고 있을 때에 한합니다. DFS 알고리즘으로도 풀 수 있지만, 그렇게 하면 시간초과가 납니다. 아래는 해당 문제의 링크입니다. https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10.. 2019. 12. 24. 백준 #1016 제곱 ㄴㄴ수 이번 문제는 1을 제외한 제곱수로 나누어 떨어지는 수를 구하는 것입니다. 에라토스테네스 체의 확장판이라고 생각하시면 될 것 같네요. 그리고 숫자의 범위는 작지만 숫자 자체가 꽤 커서 소수를 꽤 많이 구해야 합니다. 어떤 수 \(n\)이 소수인지는 \(O(\sqrt{n})\)의 복잡도로 판단할 수 있어서, 숫자가 \(10^{12}\) 오더이긴 하지만 제곱수이기 때문에 실제 구해야할 소수는 \(10^6\) 오더입니다. 계산량으로 보면 제한시간의 절반 이하로 가능합니다. 그런데 정답비율은 18%로 아주 낮습니다. 문제는 아래의 링크에 있습니다. https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,.. 2019. 12. 24. 백준 #1012 유기농 배추 텃밭에 배추가 심어져 있는데, 유기농으로 배추를 기르기 위해서 배추 흰지렁이를 풀어놓고자 합니다. 배추 흰지렁이는 배추가 모여있는 곳에는 한마리만 풀어놓아도, 인접한 배추로 옮겨다니면서 해충을 예방할 수 있습니다. 이 문제는 섬의 갯수 문제 등 자주 나오는 문제로, 그래프 이론 중 가장 기초적인 DFS, BFS 알고리즘을 이용해서 해결할 수 있습니다. 아래는 백준 사이트의 문제 링크입니다. https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이.. 2019. 12. 22. 이전 1 ··· 5 6 7 8 9 10 11 다음 728x90
