[Python][백준 18222번] 문자열
# https://www.acmicpc.net/problem/18222 import sys from collections import deque, defaultdict,Counter sys.stdin = open("input.txt", "rt") sys.setrecursionlimit(100000) from copy import deepcopy import itertools k = int(input()) # 첫번째 , 2번째라면, 바로 return if k == 1 : print(0) exit(0) if k == 2 : print(1) exit(0) # 1) 해당 k라는 숫자가, 몇번째 문자를 만드는데 쓰이는가.를 찾기 # 1,1,2,4,8,16,32 # dp[i] = i번째 문자의 길이 = 2^(i-1..
더보기
[Python][백준 12886번] 돌그룹
# https://www.acmicpc.net/problem/12886 ''' 정점 : 돌에 있는 돌의 개수 ( A, B, C ) 간선 : ( A, B, C ) -> ( A``, B``, C`` ) 정점의 개수 : ( 최대값 500 ) ^ 3 ?? 아니다. 한 집단에, 최대 정점이 몇개까지 올 수 있는지를 생각해야 한다 500 499 500 500 998 1 1000 498 1 즉, 한집단에 올 수 있는 정점의 최대개수는 1000 개가 되는 것이다 따라서 , 정점의 최대개수는 1000 ^ 3 너무 크다. 10억이라는 크기 자세히 생각해보면, 3개 집단에 있는, 전체 돌의 개수는 변하지 않는다 500 499 500 500 998 1 1000 498 1 위의 변화 과정에서도, 유일하게 변하지 않..
더보기
[Python][백준 1922번] 네트워크 연결 ( 프림, 크루스칼 )
# 크루스칼 ---- def find_parent(arr, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union(arr, a, b): # 맨처음에는 자기 자신의 값으로 parent가 설정되어 있다 ex) 1, 4 # 이 경우에는, 그냥 큰 애에다가, 작은 애를 합친다 a = find_parent(arr, a) b = find_parent(arr, b) if a > b: parent[b] = a else: parent[a] = b n = int(input()) m = int(input()) edges = [] parent = [-1] * (n+1) res = 0 # 부모 정보 초기화 for i ..
더보기
[Python][백준 14888번] 마법사상어와파이어볼
# https://www.acmicpc.net/problem/20056 from copy import deepcopy import sys from collections import deque, defaultdict, Counter sys.stdin = open("input.txt", "rt") sys.setrecursionlimit(100000) dx = [-1, -1, 0, 1, 1, 1, 0, -1] dy = [0, 1, 1, 1, 0, -1, -1, -1] N, M, K = map(int, input().split()) table = [[[] for _ in range(N)] for _ in range(N)] for _ in range(M): r, c, m, s, d = list(map(int, i..
더보기
[Python][백준 14888번] 연산자 끼워넣기
# https://www.acmicpc.net/problem/14888 import collections from collections import deque, Counter import sys import heapq sys.stdin = open("input.txt", "rt") sys.setrecursionlimit(100000) ''' 먼저 모든 수열을 입력받고, 순열을 만들어 저장할 배열을 설정한다 + 0, - 1, * 2, // 3 으로 설정한다. 각 순열 조합에 대한, 결과들을 배열에 모두 저장해서 그 중에서 최대, 최소를 선택하면 된다 즉, 특정 순열에 대한, 결과값이 각각 다르게 나올 것이라는 것이다. ''' def next_permutation(a): i = len(a) - 1 # 여기서..
더보기