반응형 Programming/BOJ257 백준 #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. 백준 #1021 회전하는 큐 회전하는 큐 문제는 큐의 성질만 잘 이해하면 풀 수 있는 문제라고 보입니다. 정답률도 낮은 번호대 치고는 43%도 괜찮고요. 3가지 연산이 가능한 회전하는 큐는, 1. 데이터 뽑아내기, 2. 왼쪽으로 한칸 회전, 3. 오른쪽으로 한칸 회전이 있습니다. 원하는 숫자 위치들을 뽑아낼 때, 2번과 3번의 동작을 최소한으로 하는 문제입니다. 얼듯보면 최적화 문제일 것같지만, 굳이 최적화 문제로 거론될 문제는 아닙니다. 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내.. 2019. 12. 25. 백준 #1019 책 페이지 한지민은 책을 좋아해서 도서관에서 근무한다. 그녀는 봄의 어느날 밤 책을 읽다가 문득 자신이 넘긴 책장에 있는 페이지에 얼마나 많은 숫자가 적혀있는지 궁금해졌다. 책의 페이지는 1 페이지부터 N 페이지까지 있다. 그녀가 읽은 책에는 과연 숫자가 몇개나 페이지에 적혀있는지 계산해보자. 원래 문제와는 조금 다르지만, 문득 한지민씨가 출연한 봄밤과 문제에 있는 지민이라는 이름이 겹쳐서 문제 내용을 바꾸어 보았습니다. 원래 문제는 아래의 링크에 있습니다. 난이도는 Gold I 문제입니다. https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 출력한다. www.acmicpc.ne.. 2019. 12. 25. 백준 #1018 체스판 다시 칠하기 블랙과 화이트가 일정규칙이 아닌 체스 보드가 있습니다. 체스판은 블랙과 화이트가 교차되어 나열되어있고, 세로방향도 마찬가지입니다. 총 8칸, 8열이 있어서, 32칸의 블랙칸과 32칸의 화이트칸이 서로 같은색끼리는 인접하지 않고 있습니다. 이번 문제는 블랙과 화이트가 엉망인 체스 보드에 칠을 최소한으로 칠하고자 할 때, 칠한 횟수를 구하는 것입니다. 더구나 이 체스 보드는 8x8 보다 클 수도 있어서, 칠하는 횟수를 적게할 수 있도록 8x8 구역도 정해야 합니다. 백준 사이트의 문제는 아래의 링크에 있습니다. https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘.. 2019. 12. 24. #1017 소수쌍(네트워크 플로우) 처음 이 문제를 접했을 때에는 '혹시 쌍둥이 소수' 문제일까 하고 봤었네요. 소수쌍이 아니라 합이 소수가 되는 숫자들의 합 이야기입니다. 짝수인 N개가 주어지면, 합이 소수가 되는 쌍으로 모두 묶을 수 있다면, 첫번째 수와 묶일 수 있는 수들의 리스트를 내는 문제입니다. 난이도는 Platinum III이지만, 난이도보다는 쉬운 문제입니다. 물론 네트워크 플로우 알고리즘을 알고 있을 때에 한합니다. DFS 알고리즘으로도 풀 수 있지만, 그렇게 하면 시간초과가 납니다. 아래는 해당 문제의 링크입니다. https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10.. 2019. 12. 24. 이전 1 ··· 38 39 40 41 42 43 다음 728x90
