[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 # 여기서..
더보기
[Python][백준 15989번] 123더하기4
# https://www.acmicpc.net/problem/15989 ''' 합을 이루고 있는 수의, 순서만 다른 것은, 같은 것으로 한다 ==> '1개' 즉, 다른 말로 하면 '구성은 같지만, 순서는 다르다' '구성은 같다?' - 사용한 1,2,3 의 개수가 같다.는 것을 의미한다 그렇다면 '중복없이 센다'는 것은 어떠한 것을 의미할까 ? - "원하는 순서로 되어있는 합"만 구하는 것이다 - 각각의 구성에서 "대표"를 만들어보는 것이다 - ex) 1+1+2, 1+2+1, 2+1+1 --> 1+1+2 를 대표로 삼는다 - '대표'를 삼는 다양한 방법이 있지만, 그중에서 '오름차순'도 가능하다 - 이 경우, 1->2->3 순서로 이루어진 '대표'를 세는 것과 같다 - 반대로 말하면, 특정 숫자를 1,2,..
더보기