[백준] 5557번 1학년 _ Python

2023. 11. 21. 14:05·Algorithms/DP

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

 

 

 

[초기 접근 방법(o)]

1. 먼저 dp 메모제이션 할 배열을 정의하자

 

2. dp[i][j] : i번째 수까지 보았을 때, 수식을 만들어서 j가 나오는 경우의 수

     - 0 <= i <= N-1, 모든 수를 끝까지 보자. (결국 0이 나오면 등식이 성립한 꼴)

     - 0 <= j <= 20, 나오는 수는 0이상 20이하이어야 한다.

 

3. 점화식

dp[i][j] += dp[i-1][j-lst[i]]

dp[i][j] += dp[i-1][j+lst[i]]

이전 i-1번째까지 보았을 때, 현재 j +- lst[i] 하여 i번째에서 j가 나오는 수를 구한다.

 

 

[생각]

'초기 접근 방법'으로 풀었는데 틀렸다.

음.. dp 배열의 정의와 점화식은 맞았으나, 모든 수를 끝까지 본 게 원인이었다.

 

0 0 0 인 경우문제에서 원하는 답은 2개이다. (0+0=0, 0-0=0)하지만 위의 접근대로 풀 경우 4개가 나온다., (0+0+0, 0+0-0, 0-0+0, 0-0-0)

 

 

 

[코드]

# 풀이 시간 : 40분
# 시간복잡도 : O(21N)
# 공간복잡도 : O(21N)
# 참고 : -

N = int(input())
lst = list(map(int, input().split()))

# dp[i][j] : i번째 수까지 보았을 때, 수식을 만들어서 j가 나오는 경우의 수
    # 0 <= i <= N-1  // 모든 수를 끝까지 보자. (결국 0이 나오면 등식이 성립한 꼴)
    # 0 <= j <= 20 // 나오는 수는 0이상 20이하이어야 한다.

# 모든 수를 끝까지 본 게 패착
# 0 0 0 인 경우 : (+, +) (+, -) (-, +) (-, -) 4개가 나온다.

dp = [[0] * 21 for _ in range(N)]

# 초기 dp 설정
# 0번째 수까지 보았을 때, 0번째 수가 나오는 경우는 본인 자신 1개이다.
dp[0][lst[0]] = 1

for i in range(1, N-1): # 마지막 수 제외
    for j in range(21):
        # 이전 dp값에서 현재 lst값을 +- 하여 범위에 맞을 경우
        # 경우의 수를 카운트 해주면 된다.
        if 0 <= j - lst[i] <= 20:
            dp[i][j] += dp[i-1][j-lst[i]]

        if 0 <= j + lst[i] <= 20:
            dp[i][j] += dp[i-1][j+lst[i]]

# 마지막 수를 제외한 idx까지 보았을 때, 수식을 만들어서 lst[-1]이 나오는 경우의 수를 출력하면 된다.
print(dp[N-2][lst[-1]])
저작자표시 (새창열림)

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

[백준] 7579번 앱 _ Python  (0) 2024.02.23
[백준] 14925번 목장 건설하기 _ Python  (1) 2024.01.30
[백준] 2228번 구간 나누기 _ Python  (0) 2023.11.24
[백준] 17626번 Four Squares _ Python  (0) 2023.11.23
[백준] 17626번 Four Squares _ Python  (0) 2023.11.17
'Algorithms/DP' 카테고리의 다른 글
  • [백준] 14925번 목장 건설하기 _ Python
  • [백준] 2228번 구간 나누기 _ Python
  • [백준] 17626번 Four Squares _ Python
  • [백준] 17626번 Four Squares _ Python
wch_t
wch_t
끄적끄적(TIL)wch_t 님의 블로그입니다.
  • wch_t
    끄적끄적(TIL)
    wch_t
  • 글쓰기 관리
  • 전체
    오늘
    어제
    • 분류 전체보기 (171)
      • Architecture (0)
      • Algorithm (67)
        • Math (5)
        • Simulation (1)
        • Data Structure (4)
        • DP (7)
        • Brute Fource (10)
        • Binary Search (6)
        • Greedy (2)
        • Graph (11)
        • Mst (1)
        • Shortest path (10)
        • Two Pointer (1)
        • Tsp (3)
        • Union Find (2)
        • Mitm (1)
      • CS (2)
        • 데이터베이스 (5)
        • 네트워크 (5)
      • DB (6)
      • DevOps (17)
        • AWS (9)
        • Docker (1)
        • CI-CD (5)
      • Error (1)
      • Project (0)
        • kotrip (0)
      • Spring (59)
        • 끄적끄적 (5)
        • 기본 (9)
        • MVC 1 (7)
        • MVC 2 (11)
        • ORM (8)
        • JPA 1 (7)
        • JPA 2 (5)
        • Spring Data Jpa (7)
      • Test (2)
      • TIL (6)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    백준 3015 파이썬
    docker: not found
    spring-cloud-starter-aws-secrets-manager-config
    애플
    response_mode
    view algorithm
    docker
    TempTable
    Jenkins
    Merge
    scope
    form_post
    백준 17299 파이썬
    aws secrets manager
    백준 17289 파이썬
    spring-cloud-starter-bootstrap
    Sxssf
    apache poi
  • 최근 댓글

  • hELLO· Designed By정상우.v4.10.3
wch_t
[백준] 5557번 1학년 _ Python
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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