728x90
반응형
https://www.acmicpc.net/problem/2003
2003번: 수들의 합 2
첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
import java.util.Scanner;
public class Main {
public static int n, m;
public static int[] arr;
public static int cnt, ans = 0;
public static int idx1, idx2 = 0;
public static void search(int idx1, int idx2) {
cnt = 0;
if (idx1 == n) {
return;
} else {
idx2 = idx1;
while (cnt != m) {
if (idx2 >= n) {
idx1++;
search(idx1, idx2);
break;
}
cnt += arr[idx2];
idx2++;
}
if (cnt == m) {
ans++;
idx1++;
search(idx1, idx2);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
search(idx1, idx2);
System.out.println(ans);
}
}
|
cs |
투포인터라는 알고리즘 이였는데 합병정렬이였나? 거기서 포인터 2개가지고 휘적휘적 하는거랑 굉장히 비슷한 느낌이였다. 부담없이 풀수 있는 문제인듯 하다.다만 조건을 잘 걸어야 스택 오버플로우에 걸리지 않는다 ^^ ㅎㅎ;;
투 포인터 라는 개념을 몰라서 찾아봤는데 좋은 글이여서 링크를 걸어둔다. (미래의 내가 언젠가 다시 보길바라며)
https://butter-shower.tistory.com/226
[Algorithm] 투포인터(Two Pointer) 알고리즘
알고리즘 문제를 풀다보면 종종 나오는 투포인터 알고리즘! 막 꼬여가지고 ㅋㅋㅋ 저도 중간에 제대로 못짜고 그러는 경우가 많은데요, 많은 코딩테스트 문제에 등장하는 것은 아니지만 잊을만
butter-shower.tistory.com
위에 코드는 투포인터가 아니다! 이게 투포인터!
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int n, s;
public static int[] arr;
public static int cnt = 0;
public static int sum = 0;
public static int left, right = 0;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
s = Integer.parseInt(st.nextToken());
arr = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
while (true) {
if (sum == s) {
cnt++;
}
if (sum >= s) {
sum -= arr[left++];
} else if (right == n) {
break;
} else {
sum += arr[right++];
}
}
System.out.println(cnt);
}
}
|
cs |
중요한게 sum==s일 때 cnt++ 해주는 것을
if (sum >= s) {
sum -= arr[left++];
}
이 조건문 안에다 넣어줬는데 그러면 안됐다. 아예 둘을 분리해서 다른 분기문으로 빼줬어야 했다.
728x90
반응형
'알고리즘 > 완전탐색' 카테고리의 다른 글
| [JAVA 프로그래머스] lv2/ 문자열 압축 (0) | 2022.07.13 |
|---|---|
| [java 백준] 골드 4/ 1806번 부분합 (0) | 2022.04.02 |
| [java 백준] 골드 4/2580번 스도쿠 (0) | 2022.03.28 |
| [java 백준] 실버 2/ 6603번 로또 (0) | 2022.03.27 |
| [java 백준] 골드 4/ 1987번 알파벳 (0) | 2022.03.25 |
댓글