HelloMinchan
처음처럼
HelloMinchan
LinkedIn
전체 방문자
오늘
어제
  • 분류 전체보기 (306)
    • Backend (4)
      • NestJS (1)
      • Express (1)
      • Spring (2)
    • Infrastructure (1)
      • AWS (1)
    • Frontend (1)
      • Next.js (1)
    • Language & Runtime (4)
      • Java (2)
      • Node.js (2)
    • Computer Science (8)
      • Computer Networks (3)
      • Operating Systems (4)
      • OOP (1)
    • 독서 (4)
      • 데이터 중심 애플리케이션 설계 (3)
      • 객체지향의 사실과 오해 (1)
    • 회고 (4)
      • Project (2)
      • Career (2)
    • Deprecated (280)

채널

  • GitHub
  • LinkedIn

최근 글

태그

  • Database
  • 백준
  • 알고스팟Python
  • 데이터베이스
  • 알고스팟
  • 프로그래머스Python
  • front-end
  • 백준Python
  • 백준Go
  • back-end
  • 백엔드
  • 프로그래머스
  • 개발자
  • 프로그래머스C++
  • programmers
  • Algospot
  • 코딩
  • 프로그래밍
  • 백준C++
  • Baekjoon Online Judge

최근 댓글

인기 글

hELLO
HelloMinchan
Deprecated

[Baekjoon Online Judge] 백준 1182번 부분수열의 합(Python)

[Baekjoon Online Judge] 백준 1182번 부분수열의 합(Python)
Deprecated

[Baekjoon Online Judge] 백준 1182번 부분수열의 합(Python)

2020. 3. 25. 21:30

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1182번 부분수열의 합

(Python)

(글쓴날 : 2020.03.25)

 


* Baekjoon Online Judge, 백준 1182번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.


 

 

백준 1182번 부분수열의 합


1) 문제

문제 링크 : https://www.acmicpc.net/problem/1182

 

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net


2) 풀이 과정

N개의 정수로 이루어진 수열이 주어질 때 크기가 양수인 부분 수열의 합이 S가 되는 경우의 수를 구하는 문제입니다.

 

저의 경우, 브루트 포스 방식을 사용하기보단, DFS를 이용해 문제를 풀었습니다.

스택에 부분 수열을 저장하였고, 부분 수열의 합은 사실상 조합을 의미하므로 탐색 중인 index를 재귀 호출할 때 인자로 넘겨 순서만 바뀐 부분 수열들의 중복을 제거했습니다.

그렇게 완전 탐색을 하는 도중, 조건문으로 스택의 길이가 0이 아니고 합이 S인 경우의 횟수를 세어 문제를 해결했습니다.


3) 코드

 

* Python 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sys
input = sys.stdin.readline
 
 
def dfs(index, N, S, sequence):
    global answer
    global visit
    global stack
    
    if len(stack) != 0 and sum(stack) == S:
        answer += 1
 
    for i in range(index, N):
        if not visit[i]:
            stack.append(sequence[i])
            visit[i] = True
            dfs(i, N, S, sequence)
            stack.pop()
            visit[i] = False
 
 
N, S = map(int, input().split())
sequence = list(map(int, input().split()))
answer = 0
visit = [False] * N
stack = []
 
dfs(0, N, S, sequence)
print(answer)

 

저작자표시 비영리 변경금지 (새창열림)

'Deprecated' 카테고리의 다른 글

[Amazon Web Services] EC2 인스턴스에 PuTTY로 접속하는 법  (0) 2020.03.27
[Baekjoon Online Judge] 백준 14889번 스타트와 링크(Python)  (0) 2020.03.27
[Amazon Web Services] AWS란 무엇인가?  (0) 2020.03.25
[Baekjoon Online Judge] 백준 6603번 로또(Python)  (0) 2020.03.24
[Algorithm] 에라토스테네스의 체  (0) 2020.03.23
  • [Baekjoon Online Judge] 백준 1182번 부분수열의 합
  • (Python)
  • 백준 1182번 부분수열의 합
'Deprecated' 카테고리의 다른 글
  • [Amazon Web Services] EC2 인스턴스에 PuTTY로 접속하는 법
  • [Baekjoon Online Judge] 백준 14889번 스타트와 링크(Python)
  • [Amazon Web Services] AWS란 무엇인가?
  • [Baekjoon Online Judge] 백준 6603번 로또(Python)
HelloMinchan
HelloMinchan
Though you should not fear failure, You should do your very best to avoid it.

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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