[DP] 백준 문제 풀이 - 9465 스티커

2022. 7. 2. 23:58· PS 연습
목차
  1. 👩🏻‍💻 문제링크
  2.  
  3. ✍️ 아이디어

👩🏻‍💻 문제링크

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

 

9465번: 스티커

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의

www.acmicpc.net

 

✍️ 아이디어

1. 문제 이해

  • 동물원과 비슷한 문제임 스티커를 뜯는데 인접한 곳의 스티커는 못씀

2.  D[N][2] = 2행 N열의 스티커로 얻을수 있는 최대 정수 (0인경우 위에 스티커 사용, 1인경우 아래 스티커 사용, 2인경우 N열 스티커 사용 안함)

3. 처음에 스티커 사용 안하는것에 구현을 애먹었는데 그냥 이전 result에서 max 구하면 되는거였음

 

4. 나중에 깨달은 것인데 건너뛰는 경우에서는 무조건 이런 경우임 대각선으로 있는 경우

0    
  여기에 o못오니까 0

 

✍️소스코드

  • 삽질 하다가 강의 듣고 깨달음 (내 풀이)
#include <iostream>
#include <algorithm>
using namespace std;
long long result[100001][3];
int score[100001][2];
int main()
{
	int t; cin>>t;
	
	for(int i=0; i<t; i++)
	{
		int n; cin>>n;
		for(int j=0; j<=1; j++)
		{
			for(int k=1; k<=n; k++)
			{
				cin>>score[k][j];
			}
		}
		result[1][0]=score[1][0];
		result[1][1]=score[1][1];
		result[1][2]=0;
		for(int j=2; j<=n; j++)
		{
			result[j][0]=max(result[j-1][1], result[j-1][2])+score[j][0];
			result[j][1]=max(result[j-1][0], result[j-1][2])+score[j][1];
			result[j][2]=max(result[j-1][0],max(result[j-1][1], result[j-1][2]));
            //[j][2] 부분을 되게 복잡하게 구현했었음..
		}
		cout<<max(result[n][0],max(result[n][1],result[n][2]))<<'\n';
	}
}

 

  • 다른사람의 풀이 (건너 뛰는 경우를 중점으로 코드를 짠듯)
  •  dp[0][i] = buf[0][i] + dp[1][i - 2]; 인 경우는 i-1열을 건너뛴 경우이다
#include <iostream>
#include <cstdio>
 
using namespace std;
 
const int MAXN = 100000;
 
int buf[2][MAXN + 1] = { 0, };
int dp[2][MAXN + 1] = { 0, };
 
int max(int a, int b) { if (a > b) return a; return b; }
 
int bottomUp(int n) {
    for (int i = 0; i < n; i++) 
        scanf("%d", &buf[0][i]);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &buf[1][i]);
 
    dp[0][0] = buf[0][0];
    dp[1][0] = buf[1][0];
    dp[0][1] = buf[0][1] + dp[1][0];
    dp[1][1] = buf[1][1] + dp[0][0];
 
    for (int i = 2; i < n; i++) {
        dp[0][i] = buf[0][i] + max(dp[1][i - 1], dp[1][i - 2]); //[1][i-2]인 경우는 건너뛴 경우
        dp[1][i] = buf[1][i] + max(dp[0][i - 1], dp[0][i - 2]); //[0][i-2]인 경우는 건너뛴 경우
    }
 
    return max(dp[0][n - 1], dp[1][n - 1]);
}
 
int main() {
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        printf("%d\n", bottomUp(n));
    }
    return 0;
}
체감난이도 걸린시간 참고 사용 문법
상 1hour 강의 이차원 DP

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

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

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

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

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
생선묵김치찌개
[DP] 백준 문제 풀이 - 9465 스티커
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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