본문 바로가기
반응형

알고리즘 PS/투 포인터3

[백준] 1253번 - 좋다 (Java)(○) https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net N : 수의 개수 : 1 ~ 2,000 Ai : 정수 : 1 ~ 1,000,000,000 1. N개의 수 중 2개를 골라서 그 수의 합이 다른 어떤 수와 같다면 그 수를 GOOD이라고 한다. 2. 투 포인터를 이용해서 A[i] 값을 순차적으로 M으로 대입해서 투포인터 알고리즘으로 A[s] + A[e] == M 인 경우의 수를 찾는다. import java.io.BufferedReader; import java.io.Input.. 2022. 12. 28.
[백준] 1940번 - 주몽(Java)(○) https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net N : 재료의 수 : 1 ~ 15,000 M : 갑옷 필요한 재료의 수 : 1 ~ 10,000,000 1. 재료 번호 중 2개의 합이 M이 되면 갑옷이 완성된다. 2. DFS로 풀기에는 N이 너무 크다. 3. 투 포인터로 sIdx는 앞에서, eIdx는 뒤에서부터 진행하면서 합산한다. import java.io.BufferedReader; import java.io.Inpu.. 2022. 12. 28.
[백준] 2018번 - 수들의 합 5(Java)(◎) https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 1. 투포인터 알고리즘을 사용한다. 2. 1 ~ N까지의 정수를 늘어놓고 처음부터 한 수를 고정한다음, 그 다음 수부터 하나씩 더해나간다. 3. sum == N이면 count++ 한다음 그 다음수를 고정하고 다시 하나씩 더해 나간다. import java.io.BufferedReader; import java.io.InputStreamReader; import.. 2022. 12. 23.
반응형