phanre의 tistory

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 누적합을 이용하지 않으면 시간초과가 나는 문제이다. 처음에 1 2 3 4 5 를 받는다면 누적합을 구하여 1 3 6 10 15 를 배열에 저장한다 이후 포인터를 두개 생성하여 왼쪽 포인터는 0, 오른쪽 포인터는 1을 가리키게 한다. 그리고 오른쪽 포인터가 가리키는 누적합에서 왼쪽 포인터가 가리키는 누적합을 빼면 사이의 합이 구해진다. 이 방식으로 왼쪽 포인터가 배열의 크기를 넘어가지..

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 투 포인터를 이용하는 문제이다. 첫번째 인덱스와 마지막 인덱스를 가리키는 포인터를 두개 만들고 조건에 따라 포인터를 옮겨주면 된다. 오름차순으로 입력이 주어지기 때문에 포인터끼리의 합이 음수이면 왼쪽 포인터를 오른쪽으로 한칸 옮기고, 포인터값이 양수이면 오른쪽 포인터를 왼쪽으로 한칸 옮기면 된다. 그리고 포인터가 가리키는 값끼리의 합의 절대값을 min값과 비교하여 더 작다면 변경해준다. 이를..

https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 간단한 두 포인터 문제이다. 첫 포인터 위치를 0번째, 1번째 인덱스로 잡은 후 var 변수를 이용하여 알파벳 종류 수를 센다. 이후 check 배열에 각각 인덱스마다 알파벳이 나올 때 마다 값을 증가시켜 갯수를 세며 temp를 증가시킨다. 우측 포인터를 증가시키다가 알파벳 종류가 n을 넘어가는 경우 우측 포인터를 멈추고 좌측 포인터가 가리키는 인덱스의 check 값이 0이 될 때 까지 좌측 포인터를 증가..