https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 소수 판별 알고리즘 + 투포인터 알고리즘의 조합이다. 우선, 에라토스테네스의 체를 이용하여 소수를 걸러준다. N의 범위가 4백만이므로 그냥 이중 for문을 사용하면 TLE다. (소수를 거른다는 것은, 소수끼리만 따로 모아준다는 것을 뜻한다. 그렇게 된다면 자연스레 소수들은 연속되게 된다.) 거른 소수를 따로 저장해준 뒤, 이를 이용해 투포인터 알고리즘을 작동시킬 것이다. 필요한 변수들을 선언 해준 뒤, left와 right 사이의 구간합을 구해준다. 이때 구간합이 n보다 작으면 right가 가리키는 소수를 더해준다...
https://www.acmicpc.net/problem/22354 22354번: 돌 가져가기 처음 위치 기준 왼쪽에서 $5,\ 6,\ 2,\ 3,\ 4,\ 7,\ 8,\ 1$번째 돌을 순서대로 가져가면 $3$번째 돌과 $5$번째 돌을 가져갈 때 점수를 얻어 $13$점이 된다. www.acmicpc.net 내가 푼 문제중 제일 티어가 높은 문제이다.. 게다가 그리디라 생각하기가 엄청 어려웠다 우선 돌을 최적으로 가져가는 방법에 대해 설명하겠다. 1. 연속된 돌은 반드시 1개만 가져갈 수 있다 (= 연속된 돌에서는 점수를 2번 이상 얻을 수 없다) -> 이 부분은 돌들을 그려놓고 한번 해보길 바란다. 이웃한 돌들이 색이 달라야 점수를 얻는데, 이웃한 돌이 같은 색이면 애초에 점수를 얻을 수 있는 환경이 아..
https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net 이 문제를 보고, '반복 가능한 최소 길이의 부분 문자열' 을 찾으면 될 것 같았다. 없으면 1 출력해주고 어떻게 찾을까 고민하던 중, 실패함수의 마지막 값은 문자열 전체를 봤을 때의 최장 부분 문자열을 구한 것이므로 내가 찾고자 하는 '반복 가능한 최소 길이의 부분 문자열'의 길이는 전체 문자열 - 실패함수의 마지막 값을 통해 구할 수 있다! 그래서 전체 문자..
https://www.acmicpc.net/problem/16570 16570번: 앞뒤가 맞는 수열 수열 (a1, a2, ⋯, aN) 이 다음의 성질을 가지면 그 수열은 k-앞뒤수열 이라고 한다. (a1, a2, ⋯, ak) = (aN-k+1, aN-k+2, ⋯ , aN), 1 ≤ k < N 어떤 수열이 k-앞뒤수열일 때, k의 최댓값 k*를 그 수열의 앞뒤계 www.acmicpc.net 완탐하면 당연히 시간초과다. 그렇다면 어떻게 푸냐? 거꾸로 뒤집으면 된다. 수열을 거꾸로 입력받아서 그것에 대한 실패함수를 구하고, 최댓값과 최댓값이 나오는 횟수를 구해주면 된다. 근데 같은 방식인 것 같은데, 아래 코드와 정답 코드의 차이가 뭔 지 모르겠다. (더보기 클릭ㄱㄱ) 더보기 얘는 틀렸다고 한다.. why? ..
https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net 이 문제는 실패함수만 구해주면 수월하게 풀리는 문제이다. bfs, dfs, 다익스트라를 공부할 때 코드의 틀을 외우듯이 실패함수도 외우고 계속 써먹다보면 언젠가 이해가 되리라 생각한다. 실패함수를 구한 뒤, 문제에서 주어진 광고판의 크기에서 실패함수를 빼주면 되는데, 광고판의 크기가 5라면 5번째 실패함수의 값을 빼주면 된다. (인덱스니까 -1해주기) 쉽게 말해서, 6칸짜리 광고판에 4글자 문구를 띄우면, 2칸이 ..
https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 당연한 말이지만, 문제에 있는 코드로 풀면 시간초과로 틀린다. STL에 있는 sort를 활용하는데, 문제의 답은 어떻게 구하냐? pair를 이용하여 처음 입력받을 때, 숫자와 인덱스를 같이 저장해주면 된다! 버블 소트는 한번 정렬할 때 마다 제일 큰 수가 맨 뒤로 이동한다. 그렇게 되면 다른 수들은 자연스레 한칸 앞으로 움직이게 되고 버블 소트가 진행되고 난 후 배열의 인덱..
