[DP] 백준 문제 풀이 - 1912 연속합

2022. 6. 30. 00:08· PS 연습
목차
  1. 👩🏻‍💻 문제링크
  2. ✍️ 아이디어

👩🏻‍💻 문제링크

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

 

 

1912번: 연속합

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

www.acmicpc.net

 

✍️ 아이디어

1. 문제 이해

  • 연속해서 더할수 있는 수중에 가장 큰 수를 찾자

2. 점화식 D[ i ] = i번째 수로 끝나는 가장 큰 연속합

3. i번째 수열과 i-1번째 점화값과 i번째 수열을 더한 것중에 큰것을 저장한다

A[i] < A[i]+result[i-1] //A[i]는 수열 result는 값 저장 공간

 

✍️소스코드

  • 이 아이디어는 강의 안봤으면 절대 안떠올랐을거 같다..(남의 코드는 내코드랑 비슷해서 패스~)
#include <iostream>
#include <algorithm>
using namespace std;
int result[100001];

int main()
{
	int A[100001];
	int n; cin>>n;
	for(int i=1; i<=n; i++)
	{
		cin>>A[i];
	}
	result[1]=A[1];
	for(int i=2; i<=n; i++)
	{
		if(A[i]<A[i]+result[i-1])
		{
			result[i]=A[i]+result[i-1];
		}
		else{
			result[i]=A[i];
		}
	}
	cout<<*max_element(result+1, result+n+1)<<'\n';
}

 

 

체감난이도 걸린시간 참고 사용 문법
최상 1hour 강의 참고 Dp

'PS 연습' 카테고리의 다른 글

[DP] 백준 문제 풀이 - 9465 스티커  (0) 2022.07.02
[DP] 백준 문제 풀이 - 2225 합분해  (0) 2022.07.01
[DP,백트래킹] 백준 문제 풀이 - 14002 가장 긴 증가하는 부분 수열 4  (0) 2022.06.29
[DP] 백준 문제 풀이 - 11053 가장 긴 증가하는 부분 수열  (0) 2022.06.27
[DP] 백준 문제 풀이 - 10844 쉬운 계단 수  (0) 2022.06.26
  1. 👩🏻‍💻 문제링크
  2. ✍️ 아이디어
'PS 연습' 카테고리의 다른 글
  • [DP] 백준 문제 풀이 - 9465 스티커
  • [DP] 백준 문제 풀이 - 2225 합분해
  • [DP,백트래킹] 백준 문제 풀이 - 14002 가장 긴 증가하는 부분 수열 4
  • [DP] 백준 문제 풀이 - 11053 가장 긴 증가하는 부분 수열
생선묵김치찌개
생선묵김치찌개
생선묵김치찌개
준혁's 코딩 연구기록
생선묵김치찌개
전체
오늘
어제
  • 분류 전체보기 (96)
    • Java (5)
    • Spring Boot (3)
    • 자료구조 (8)
    • 네트워크 (4)
    • 데이터베이스 (4)
    • 기술적 고민 (17)
      • Side Match (13)
      • 자리나따 (4)
    • C++ (3)
    • Algorithm (4)
    • PS 연습 (38)
    • 잡동사니 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • backend
  • 단순 연결 리스트
  • 큐
  • 파일 업로드
  • 예외처리
  • 스택
  • 양방향 연결 리스트
  • 브루트 포스
  • 트리
  • 재귀
  • 이진트리
  • 원형 연결 리스트
  • CPP
  • 백준 골드
  • 백준
  • aws rds
  • open api
  • 스프링
  • 완전탐색
  • 배열 리스트
  • 해커톤
  • sentry
  • dp
  • DN
  • 수식트리
  • Stream
  • 알고리즘
  • ㄱ
  • 열혈 자료구조
  • 자료구조

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
생선묵김치찌개
[DP] 백준 문제 풀이 - 1912 연속합
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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