글 읽기 - pypy3로 풀고있는데 틀렸다고 뜨네요......

blutics 4년 전 0

대충 주석은 달아놓았습니다.

부탁드립니다!!ㅠ

from math import factorial
from math import gcd

import sys
input=sys.stdin.readline
N=int(input())
num=[0]*N          # 숫자들을 저장하는 리스트
num_len=[0]*N      # 각 숫자들의 길이를 저장하는 리스트
for i in range(N): # num과 num_len을 채우는 과정
    t=input()
    num[i]=int(t)
    num_len[i]=len(t)
k=int(input())
full=2**N-1
# bit에 의해 생성되는 전체 경우의 수 ex) 111111111
each_bit=[2**i for i in range(N)]
# 1 10 100 1000 10000 100000 각각의 비트를 선택하기 위해 리스트에 저장(2비트)
plen=sum(num_len)//주어진 집합의 숫자들의 순열에 의해 만들어지는 수의 길이
rm=[[0]*plen for i in range(N)]
# 주어지는 집합에서 주어지는 숫자들이 위치에 따라서 달라지는 나머지 수
# ex) 423라는 수가 주어진다면 423000 42300 4230 423에 대한 각각의 나머지를 저장
for i in range(N):
    mx=plen-num_len[i]
    for j in range(mx+1):
        rm[i][j]=num[i]*10**(mx-j)%k
dp=[[-1]*(full+1) for _ in range(100)]

def solve(length, bit, remain):
    if bit==full:
        return remain==0
    if dp[remain][bit]!=-1:
        return dp[remain][bit]
    dp[remain][bit]=0
    for n in range(N):
        if not bit & each_bit[n]:
            dp[remain][bit]+=solve(length+num_len[n], bit | each_bit[n],(remain+rm[n][length])%k)
    return dp[remain][bit]

result=solve(0,0,0)
g=gcd(result,factorial(N))
# print(result, g)
if result==0:
    print("0/1")
else:
    print("%d/%d"%(result//g, factorial(N)//g))

blutics 4년 전 1

sys.stdin.readline은 단순히 입력된 값만 받아오는게 아니라 \n도 같이 받아오기 때문에

받아온 문자열을 그대로 사용하면 +1이 됩니다.

후..... 하루 종일 이거잡고 디버깅했는데 여기서 틀렸을 줄이야......

앞으로는 디버깅 할때는 알고리즘 로직에서 발생하는 데이터만 볼게 아니라

처음 시작할때 세팅한 데이터도 확인해야겠네요.

결과값이 답과 비슷하게 나와서 로직에서 문제가 발생한 줄 알았는데 ㅠ

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

문제

문제

출처

ICPC

pypy3로 풀고있는데 틀렸다고 뜨네요......

blutics 4년 전 0

blutics 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말