소프티어

이거 파이썬은 시간초 더 주셔야 할 것 같아요 ㅠㅠ

import sys from collections import defaultdict # N : 사람 수, M : 문자열 길이 N, M = map(int, sys.stdin.readline().split()) cpti = [int(sys.stdin.readline().rstrip(), 2) for _ in range(N)] # 키가 없어도 기본값 0으로 할당 dct = defaultdict(int) same_pair = 0 for i in range(N): same_pair += dct[cpti[i]] # 이전의 사람 중 똑같은 cpti를 가진 사람의 수 만큼 쌍을 더해줌 # 비트 1개 반전 시키는 용도 for j in range(M): # 모든 수와 0의 xor 연산은 자기 자신이 됨 # 따라서 반전 시키고 싶은 비트에 1을 두면 그 자리의 수가 반전 됨 new_cpti = cpti[i] ^ (1 << j) # 한 가지 영역이 다른 cpti same_pair += dct[new...

[CPTI] 타임아웃 기준을 못맞추겠어요

import sys input = sys.stdin.readline N, M = map(int, input().strip().split()) people = [int(input().rstrip(), 2) for _ in range(N)] ans = 0 for i in range(N-1): p1 = people[i] for j in range(i+1, N): if bin(p1^people[j])[2:].count('1') < 3: ans += 1 print(ans) 3초 기준에 3.08x 초로 계속 실패하는데 어떻게 해도 실패하네요. O(N^2M) 보다 더 빠르게 못할 것 같은데.

java 정답 코드

O(N^2) 버전 import java.util.*; // 1.982s , 31.03MB public class Main_N_Squre {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int N = sc.nextInt();         int M = sc.nextInt();                 // CPTI 입력 받기         int[] cptiList = new int[N];         for(int i = 0; i < N; i++) {             String cpti = sc.next();             cptiList[i] = Integer.parseInt(cpti, 2);         }                 // 전체 친밀감을 느끼는 쌍의 수 계산     ...