투포인터

https://www.acmicpc.net/problem/13144문제 요약길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성시간 제한1초입력첫 번째 줄에는 수열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)두 번째 줄에는 수열을 나타내는 N개의 정수가 주어진다.수열에 나타나는 수는 모두 1 이상 100,000 이하이다.출력조건을 만족하는 경우의 수를 출력접근법먼저 정답 변수에 연속부분수열 길이가 1인 개수를 미리 더해줌이후는 투포인터로 가능한 개수를 구하려고 했다.s = 0, e = 1부터 시작여기서 e가 가리키는 숫자를 포함한 연속 부분 수열의 개수는 e보다 앞에 있는 숫자들의 개수에 영향을 받는다..

https://www.acmicpc.net/problem/14527문제 요약M마리의 소(짝수마리) M/2쌍으로 나누어 각각의 쌍으로 나누어 동시에 젖을 짜는 외양간으로 보내려고 한다.각 외양간에서 두 소의 젖을 짜는 데 걸리는 시간은 두 소의 젖 생산량의 합과 같다.즉, 젖을 짜는 시간이 각 쌍의 소들의 젖 생산량의 합에 따라 달라진다.최적의 소 짝을 찾아 젖 짜는 작업을 완료하는 최소 시간을 계산하라시간 제한2초입력N개의 줄이 주어지며 각 줄에는 x와 y가 주어진다x는 y 단위의 젖 생산량을 가진 소들의 수를 의미M은 x들의 총합으로, 즉 모든 소들의 총합1 ≤ N ≤ 10만1 ≤ y ≤ 10억출력젖 짜는 작업을 완료하는 데 걸리는 최소 시간을 출력접근법주어질 수 있는 소 마리수의 총합 M은 10억 개..

알고리즘 문제) BOJ 31589. 포도주 시음 링크 : https://www.acmicpc.net/problem/31589문제 요약N종류의 포도주가 존재하며, 각각 맛을 지니고 있다이때, 첫 잔을 마실 때는 포도주 본연의 맛을 느끼지만그 이후부터 맛있는 포도주를 마시다가 맛없는 포도주를 마시면 0의 맛을 느끼며맛없는 포도주를 마시다가 맛있는 포도주를 마시면 두 포도주의 맛의 차이만큼 느낀다이때 K종류의 포도주만 마신다 했을 때, 최대로 느낄 수 있는 맛을 구해라시간 제한1초입력포도주의 수 N, 마셔야할 포도주 수 K1 ≤ K ≤ N ≤ 30만N개의 포도주 맛 Ti가 주어진다1 ≤ Ti ≤ 10억출력맛의 합의 최댓값은?접근법순차적으로 먹게 될 경우 맛의 차이만큼 먹게된다.이때, 순차적으로 먹게 될 경우 ..

알고리즘 문제) BOJ 1562. 계단 수 링크 : https://www.acmicpc.net/problem/1562문제 요약계단 수 : 인접한 모든 자리의 차이가 1N이 주어질 때 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단수가 총 몇 개인지 구하기시간 제한2초입력첫째줄에 N이 주어진다.1 ≤ N 출력정답을 1000000000로 나눈 나머지 출력접근법비트마스크 공부 다시하고 풀었다.N이 100까지 가능하고 각각 들어갈 수 있는 숫자가 0~9이기때문에 최악의 경우 나올 수 있는 경우의 수가 9^100으로 그냥 백트랙킹으로 풀면 안된다.나는 탑다운DP 알고리즘으로 풀었다.recur(int cur, int prv, int numCnt)cur → 현재 가리키는 자릿수(앞에서부터 하나씩 쌓아감)pr..

알고리즘 문제) BOJ 12015. 가장 긴 증가하는 부분 수열 2 링크 : https://www.acmicpc.net/problem/12015문제 요약수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열 길이 출력하기예를들어, A={10,20,10,30,20,50}인 경우, 가장 긴 증가하는 부분 수열 길이는 {10,20,30,50}으로 4이다.시간 제한1초입력수열 A의 크기 N1 ≤ N ≤ 100만수열 A를 이루고 있는 Ai1 ≤ Ai ≤ 100만출력수열 A의 가장 긴 증가하는 부분 수열 길이 출력접근법수열 A의 크기 N이 최대 100만까지 가능하므로 2중 for문을 사용하면 안된다.이분탐색으로 어떻게 푸는건지 모르겠어서, 다른 분의 아이디어를 참고했다예시로 2 3 1 5 4 1 8 이 주어졌다 했을..

알고리즘 문제) BOJ 1946. 신입 사원 링크 : https://www.acmicpc.net/problem/1946문제 요약서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발즉, A의 성적이 다른 B의 성적에 비해 서류와 면접 모두 떨어지면 선발 X시간 제한2초입력테스트 케이스 개수 T1≤T≤20각 테스트케이스의 첫째 줄에 지원자 수 N1≤N≤10만N개의 줄에 지원자의 서류, 면접 성적이 주어짐동석차 X출력선발할 수 있는 신입사원 최대 인원수 구하기접근법나랑 다른 지원자 모두를 비교했을 때 서류, 면접 석차가 모두 뒤에 있으면 안 됨서류 점수 기준으로 오름차순 정렬하면1 42 53 64 25 76 17 31등은 무조건 합격2등은 1등이랑 면접 비교 ⇒ 탈락3등은 ..

알고리즘 문제) BOJ 1940. 주몽 링크 : https://www.acmicpc.net/problem/1940문제 요약갑옷을 만드는 재료들은 각각 고유 번호를 갖고 있음두 개의 재료의 고유 번호를 합쳐서 M이 되면 갑옷이 만들어짐N개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지 구해라시간 제한2초입력재료 개수 N1≤N≤15000갑옷을 만드는데 필요한 수 M1≤M≤1000만N개의 재료들의 고유 번호가 주어짐고유 번호 : 10만 이하 자연수출력갑옷을 만들 수 있는 개수접근법완전 탐색으로 생각하기2중 for문으로 재료 두 개 선택해서 M이 되는 개수를 고른다어차피 다 다른 고유 번호가 주어지기 때문에 특정 숫자가 무언가와 더해서 M이 될 수 있는 경우는 단 한가지 뿐이다.투포인터 적용하기먼저..

알고리즘 문제) BOJ 2230. 수 고르기 링크 : https://www.acmicpc.net/problem/2230문제 요약N개의 정수로 이루어진 수열 A[1], … A[N]이 존재여기서 두 수를 골랐을 때, 그 차이가 M이상이면서 제일 작은 경우를 구해라같은 수를 고를 수도 있다.시간 제한2초입력두 정수 N, MN개의 줄에 차례로 A[1], … A[N]이 주어진다.1≤N≤10만0≤M≤20억0≤abs(A[i])≤10억출력첫째 줄에 M이상이면서 가장 작은 차이 출력접근법1 2 3 4 5 6 (M=2) ses→ 1, e→1abs(s,e) = 0 e+=1s→ 1, e→ 2abs(s,e) = 1 e+=1s→ 1, e→ 3abs(s,e) = 2 == M찾았으므로 break⇒ 차이값 더 큰 차이값을 찾아야 한다..

알고리즘 문제) BOJ 24620. Sleeping in Class 링크 : https://www.acmicpc.net/problem/24620문제 요약소가 수업시간에 잠에 드는 횟수를 기록수업은 총 N번 있으며, 각 수업마다 잠든 횟수 ai 기록전체 수업동안 잠든 횟수는 100만을 넘지 않음그러나 모든 수업에서 같은 횟수만큼 잠든다고 기록하려고 함수정을 위해서는 인접한 두 수를 합치는 것⇒ 모든 숫자가 같게 만들기 위해 필요한 최소 수정 횟수는?시간 제한2초입력테스트 케이스 T(1≤T≤10)N1≤N≤10만ai0≤ai≤100출력테스트 케이스마다 숫자를 같게 만들기 위한 최소 수정 횟수를 출력접근법16 = (1,16) (2,8) (4,4)⇒ 1이 16개, 16이 1개, 2가 8개, 8이 2개, 4가 4개일..

알고리즘 문제) BOJ 20159. 동작 그만. 밑장 빼기냐? 링크 : https://www.acmicpc.net/problem/20159문제 요약N개의 카드와 2명의 플레이어N은 짝수개가 주어짐카드를 분배했을 때 카드 윗장에 적힌 수의 합이 더 큰 사람이 이김카드는 분배한 사람부터 받는다.한번만 밑장 빼기를 할 때 얻을 수 있는 최대 카드 합?밑장 빼기 : 윗장이 아닌 밑장을 보여시간 제한2초입력카드 개수 N2≤N≤10만, 짝수카드의 윗장부터 밑장까지 카드의 값 X가 정수로 주어짐1≤X≤1만출력정훈이가 얻을 수 있는 최대 카드 합?접근법밑장빼기 이해가 어려웠던 문제.. ⇒ 잘 못 이해하고 풀어서 틀림;;;;해당 턴에서 밑장을 빼면 밑장에 있는 카드를 해당 턴에 받게 되고, 그만큼 카드가 밀리게 됨 ⇒ ..