글 읽기 - 40% 까지 진행하다 틀립니다

effort98 2년 전 0

N과 M 문제를 응용해서 문제를 풀었습니다.

visit 과 overlap 을 이용하여 중복을 피했는데 틀렸다고뜨네요

대체 어디서 잘못된걸까요

import sys
n, S = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
visit = [0] * n
count = 0
s = []
def dfs():
    global count
    overlap = 0
    if s != []:
      for i in range(n):
        if visit[i] != 1 and arr[i] != overlap and arr[i] >= s[-1]:
            s.append(arr[i])
            visit[i] = 1
            overlap = arr[i]
            if sum(s) == S:
                print(s)
                count += 1
            dfs()
            s.pop()
            visit[i] = 0
    else:
      for i in range(n):
        if visit[i] != 1 and arr[i] != overlap:
            s.append(arr[i])
            visit[i] = 1
            overlap = arr[i]
            if sum(s) == S:
                print(s)
                count += 1
            dfs()
            s.pop()
            visit[i] = 0
dfs()
print(count)

ksoosung77 2년 전 3

반례입니다

5 0

0 0 0 0 0

출력

실제 답

effort98 2년 전 0

감사합니다!

항상 0을 조심해야겠네요

syzseisus 1년 전 0

@kssosung77

답 15이어야 하는 거 아닌가요?

0~0, 0~1, 0~2, 0~3, 0~4,

1~1, 1~2, 1~3, 1~4,

2~2, 2~3, 2~4,

3~3, 3~4,

4~4

이렇게 15개요

kocc10 1년 전 2

@syzseisus

순서를 고려 하지 않기 떄문에 31입니다.

0 0 0 0 0 (편의 상 1, 2, 3, 4, 5 라고 하겠습니다.)

1 2

1 3

1 4

1 5

2 3

2 4

등등 이 가능 해서 32이며 '크기가 양수인 부분수열' 이기 때문에 공집합을 제외 해서 31개입니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

40% 까지 진행하다 틀립니다

effort98 2년 전 0

ksoosung77 2년 전 3

effort98 2년 전 0

syzseisus 1년 전 0

kocc10 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말