[BOJ] 2003: 수들의 합 2

2024. 3. 22. 04:51·코테/Algorithm
728x90
 

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

 

풀이

 

배열 내에서 시작점과 끝나는 점을 옮겨주면서 합을 구해준다. (= 투포인터)

합 > M 일 경우에 start 점을 이동시키기 전에, 이전 arr[start]값을 빼줘야 했는데,

순서를 바꿔서 해놨더라 대체 어디서 안되는걸까 한참을 찾았는데 ..

 

3 1
1 2 1

답: 2

 

나는 위 테케를 해결했더니 문제가 해결 ..~!

반례라고 보기는 어렵지만 ㅎㅎ 테케가 더 많이 제공됐다면 좋았을 문제..

 

package 백준renew;

import java.io.*;
import java.util.*;

public class 실버4_2003_수들의합_2 {
	static int N, M, ans;
	static int arr[];
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		ans = 0;
		arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Check(0, 0);
		
		sb.append(ans);
		bw.write(sb.toString()); bw.flush(); bw.close();
		
	}
	static void Check(int start, int end) {
		int sum = arr[start];
		while(true) {
			if(end == N || start == N) {
				break;
			}
			if(sum < M) {
				end++;
				if(end == N) {
					break;
				}
				sum+=arr[end];
			}else if(sum > M) {
				sum-=arr[start];
				start++;
			}else {
				ans++;
				end++;
				if(end == N) {
					break;
				}
				sum+=arr[end];
			}
		}
	}
}
728x90

'코테 > Algorithm' 카테고리의 다른 글

[BOJ] 1389: 케빈 베이컨의 6단계 법칙 (JAVA)  (1) 2024.03.24
[BOJ] 3273: 두 수의 합 (JAVA)  (1) 2024.03.23
[BOJ] 14503: 로봇청소기 (JAVA)  (0) 2024.03.21
[BOJ] 18258: 큐2 (JAVA)  (0) 2024.03.19
[BOJ] 22233: 가희와 키워드 (JAVA)  (0) 2024.03.17
'코테/Algorithm' 카테고리의 다른 글
  • [BOJ] 1389: 케빈 베이컨의 6단계 법칙 (JAVA)
  • [BOJ] 3273: 두 수의 합 (JAVA)
  • [BOJ] 14503: 로봇청소기 (JAVA)
  • [BOJ] 18258: 큐2 (JAVA)
DROPDEW
DROPDEW
💻 Developer | 기록하지 않으면 존재하지 않는다
  • DROPDEW
    제 2장 1막
    DROPDEW
  • 전체
    오늘
    어제
    • Dev (420) N
      • App·Android (1)
      • BE (44)
        • HTTP 웹 기본 지식 (8)
        • 스프링 입문 - 코드로 배우는 스프링 부트, 웹 .. (12)
        • 스프링부트와 JPA 활용 (11)
        • 스프링부트 시큐리티 & JWT (0)
        • PHP (6)
      • FE·Client (23)
        • HTML (1)
        • React (19)
        • Unity (1)
      • Data (19) N
        • AI (7)
        • Bigdata (6)
        • Database (1)
        • 빅데이터분석기사 (4) N
      • Infra (0)
      • Activity (1)
        • Education (0)
        • Intern (0)
        • 리모트 인턴십 6기 (1)
        • 구름톤 유니브 4기 (0)
        • SW교육기부단 15기 (0)
      • CS (8)
      • 취준 (13)
        • 자격증 (4)
        • 인적성·NCS (6)
        • 코테·필기·면접 후기 (3)
      • 코테 (270)
        • Algorithm (222)
        • SQL (35)
        • 정리 (13)
      • 인사이트 (27)
        • 회고 (0)
        • 금융경제뉴스 (7)
        • 금융용어·지식 (2)
        • 북마크 (7)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    티스토리챌린지
    그리디알고리즘
    자료구조
    그래프탐색
    최단경로
    다이나믹프로그래밍
    이분탐색
    문자열
    수학
    그래프이론
    구현
    백준
    정렬
    누적합
    브루트포스 알고리즘
    시뮬레이션
    투포인터
    매개변수탐색
    너비우선탐색
    오블완
  • 최근 댓글

  • 최근 글

  • 250x250
  • hELLO· Designed By정상우.v4.10.3
DROPDEW
[BOJ] 2003: 수들의 합 2
상단으로

티스토리툴바