본문 바로가기

투 포인터

[백준 22945] 팀 빌딩 (JAVA)

CodingTEST 2023. 11. 15. [백준 22945] 팀 빌딩 (JAVA) 백준 22945번 문제 - 팀 빌딩 22945번: 팀 빌딩 개발자 $N$명이 팀 빌딩을 위해 한 줄로 서있다. 하나의 팀을 만들기 위해서는 개발자 2명이 반드시 모여야 한다. 개발자 A와 개발자 B가 팀을 만들 때 팀의 능력치는 아래와 같이 계산이 된다. (개 www.acmicpc.net 문제 분석 개발자 2명 이상의 팀이 만들어져야하며, 이 때 해당 팀의 능력치는 [양끝에 있는 개발자 중에 낮은 능력치 * 개발자 수 -2] 이다. 그럼 n명의 개발자가 순서 있이 주어졌을 때 가장 큰 팀 능력치를 구해라 해결 키 포인트 투포인트로 문제 풀이 개발 능력치는 양끝 사람의 능력치가 중요하므로 포인터를 양끝에 둔다. 포인터가 만났거나 추월했을 때 반복 종료되는 반복문 최대값과 비교해 현재 팀이 최대값이면 최대값..

[백준 22862] 가장 긴 짝수 연속한 부분 수열 (JAVA)

CodingTEST 2023. 11. 13. [백준 22862] 가장 긴 짝수 연속한 부분 수열 (JAVA) 백준 22862번 문제 - 가장 긴 짝수 연속한 부분 수열 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 문제 분석 수열에서 최대 K번 숫자를 삭제해 가장 긴 짝수 연속한 부분 수열 길이를 출력해라 해결 키 포인트 투포인트로 문제 풀이 최대 K번 삭제 (무조건 K번을 삭제할 필요 없다) 은근 까다로웠던 부분 : K가 0이어도 뒤에 홀수가 나오기 전에는 end가 증가해도 된다. 나는 처음 알고리즘을 짤 때 K가 0번이 되기 전까지 end를 증가 시켰다. → 하지만 K가 0번일때까지 end를 증가해도 됨 투 포인터 문제 연속한 부분 수열 문제 ..

[백준 20922] 겹치는 건 싫어 (JAVA)

CodingTEST 2023. 11. 13. [백준 20922] 겹치는 건 싫어 (JAVA) 백준 20922번 문제 - 겹치는 건 싫어 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 문제 분석 문제 분석 숫자 N개를 입력 받고, 숫자가 K이하로 중복되도록 최장 연속 부분 수열의 길이를 출력 해결 키 포인트 투포인트로 문제 풀이 중복 수 판단 처음에 중복을 어떻게 알아낼까 고민함 Map을 사용해서 중복되는 숫자가 있는지 확인 맵은 입력숫자, 중복 개수로 판단 → 시간 초과(put, get을 많이해서 그런지..(?)) 입력받을 수 있는 수가 100000까지니 100001개 배열 만들어서 중복 개수 ..

[백준 1940] 주몽 (JAVA)

CodingTEST 2023. 3. 4. [백준 1940] 주몽 (JAVA) 백준 1940번 문제 - 주몽 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 문제 분석 N과 M, 그리고 N개의 수를 입력 N개의 수 중 두 개의 수를 합해 M이 되는 수의 개수 출력 해결 키 포인트 배열 정렬 - Arrays.sort() 함수 이용 투 포인트 사용 생각하지 못한 문제 코드를 보기 쉽게 하기 위해 num[start]+num[end] 을 sum이라는 변수로 두었다. Long sum = num[start]+num[end]; 하지만 이게 문제가 되었다. → 정확한 이유는 ..

[백준 1253] 좋다 (JAVA)

CodingTEST 2023. 3. 4. [백준 1253] 좋다 (JAVA) 백준 1253번 문제 - 좋다 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제 분석 N과 N개의 수를 입력 입력받은 수를 다른 입력받은 두 개의 수의 합으로 나타낼 수 있는 수 → "좋은 수" "좋은 수"의 개수를 출력 해결 키 포인트 배열 정렬 - Arrays.sort() 함수 이용 투 포인트 사용 생각하지 못한 반례 두수에는 확인하고자 하는 자신의 수는 포함하지 않음 입력 출력 3 0 0 1 0 입력 값에는 음수 값이 존재할 수 있음 입력 출력 5 0 -1 -1 1 1 5 코드 import java.io.BufferedReade..

이전 1 다음

티스토리툴바