[백준] 13398 연속합 2

2024. 3. 8. 18:18· Algorithm/백준 문제풀이
목차
  1. 문제 출저
  2. 문제 풀이
  3. 소스 코드

 

 

 

문제 출저

https://www.acmicpc.net/problem/13398

 

13398번: 연속합 2

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

www.acmicpc.net

 

 

 

문제 풀이

수열에서 연속하는 몇 개의 수를 선택해 가장 큰 합을 구해야 한다. 이 때, 한 개의 수는 선택하지 않아도 된다. 

 

DP를 이용하여 문제를 풀었습니다.

다만 숫자를 하나 뺄 때, 빼지 않을 때 2가지 경우의 수를 염두해야 합니다. 

 

dp = new int[n][2];

0은 빼지 않았을 경우, 1은 뺀 경우입니다. 

 

dp[n][0] 일 때는 뻰 경우 입니다. 

전의 값(i - 1)과 수열의 더한 값, 수열의 값을 비교하여 더 큰 값을 저장합니다. 

dp[i][0] = Math.max(dp[i-1][0] + board[i], board[i])

 

dp[n][1] 일 때는 숫자 하나를 제외한 경우 입니다. 

하나를 제외하지 않은 dp의 이전값 ( dp[i-1][0] ) , 하나를 제외한 dp에서 수열의 값을 더한 값(dp[i -1][1] + board[i])을 비교하여 더 큰 값을 저장합니다. 

dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1] + board[i])

 

answer 변수를 하나 선언하여 dp[i][0], dp[i][1] 값 중 큰 값을 업데이트하여 최종 정답을 구합니다. 

 

 

 

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
연속합 2
https://www.acmicpc.net/problem/13398
 */

public class Main {

    static int n;
    static int[] board;
    static int[][] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        board = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            board[i] = Integer.parseInt(st.nextToken());
        }



        dp = new int[n][2];

        dp[0][0] = board[0];
        if (board[0] > 0) dp[0][1] = board[0];
        else dp[0][1] = 0;

        int answer = board[0];

        for (int i = 1; i < n; i++) {

            // 특정 수를 제거하지 않을 경우
            dp[i][0] = Math.max(dp[i - 1][0] + board[i], board[i]);

            // 특정 수를 제거하는 경우
            // 1. 현재 위치의 특정 수를 제거한 경우
            // 2. 현재 위치 이전에 특정 수를 제거한 경우
            dp[i][1] = Math.max(dp[i-1][0], dp[i - 1][1] + board[i]);

            answer = Math.max(answer, Math.max(dp[i][0], dp[i][1]));
        }

        System.out.println(answer);




    }

}

 

  1. 문제 출저
  2. 문제 풀이
  3. 소스 코드
'Algorithm/백준 문제풀이' 카테고리의 다른 글
  • [백준] 15661 링크와 스타트 - Java
  • [백준] 9084 동전 - Java
  • [백준] 1940 주몽 - Java
  • [백준] 16472 고냥이 - Java
너지살
너지살
너지살
너지살개발자
너지살
전체
오늘
어제
  • 분류 전체보기 (375)
    • 잡식 (2)
      • 티스토리 (2)
    • 개발 일지 (0)
      • OMS 프로젝트 (4)
      • 우테코 6기 프리코스 (1)
    • Git (2)
    • JAVA (15)
      • Java 공부 (6)
      • 자료구조 (4)
      • 도움되는 메모 (4)
    • DevOps (18)
      • AWS (6)
      • Docker (2)
      • Jenkins (1)
      • Nginx (1)
      • Kafka (6)
      • RabbitMQ (2)
    • Spring, Spring Boot (16)
      • Test Code (1)
      • AOP (2)
      • Batch (3)
      • Cache - Redis (5)
      • Cloud Config - 설정 파일 관리 (3)
      • 성능 측정 (1)
      • 예외 처리 (1)
    • BackEnd (1)
      • Spring 공부 (1)
      • Thymeleaft (0)
    • DB (17)
      • JPA (2)
      • DB 공부 (3)
      • DB 포스팅 (4)
      • DB 답장 (1)
      • MySQL (2)
      • Redis (5)
      • MongoDB (0)
    • CS (8)
      • Spring (4)
      • DataBase (3)
      • Java (1)
    • Algorithm (203)
      • 알고리즘 개념 (5)
      • 정렬 알고리즘 (11)
      • 프로그래머스 문제풀이 (18)
      • 백준 문제풀이 (165)
      • 소프티어 문제풀이 (3)
      • 알고리즘 시험 정리 (1)
    • SQL (0)
      • 문법 (1)
      • 프로그래머스 문제풀이 (52)
      • 리트코드 문제풀이 (19)
    • IT (1)
      • IT 공부 (1)
    • 정리 (10)
      • 질문 정리 (10)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • redis
  • 최소 신장 트리
  • 유니온파인드
  • Next permutation
  • 우선수위큐
  • 부분탐색
  • 분리 집합
  • 비트마스킹
  • Algorithm
  • Test code
  • 다음 순열 찾기
  • DFS
  • 설정
  • Bitmast
  • DP
  • 투포인트
  • 질문 정리
  • db
  • Java 정리
  • 크루스칼 알고리즘
  • 그래프 이론
  • 최소 스패닝 트리
  • 병렬 처리
  • 다이나믹프로그래밍
  • MST
  • 두 포인터
  • 다이나믹 프로그래밍
  • 소프티어
  • cache
  • 자료구조
  • Sorting algorithm
  • 투 포인터
  • docker
  • dynamic programing
  • JPA
  • git
  • 그래프 탐색
  • Spring Boot Redis 연결
  • Spring Batch
  • 깊이/너비 우선탐색
  • two pointer
  • Java
  • 알고리즘
  • 데이터베이스
  • dynamiceprogramming
  • Union-Find
  • 백준
  • 경로표현식
  • 외판원 순회 문제
  • Spring Boot

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
너지살
[백준] 13398 연속합 2
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.