본문 바로가기

전체 글

[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,.. 더보기
[Python][백준 9095번] 123 더하기 n = int(input()) m = 3 nums = [1, 2, 3] dp = [0]*11 dp[0] = 1 for i in range(len(dp)): for j in range(m): if i - nums[j] >= 0: dp[i] += dp[i-nums[j]] print("dp", dp) 더보기
[Python][백준 17822번] 원판돌리기 # https://www.acmicpc.net/problem/17822 # 첫번째 시도 import copy import heapq as hq import sys from functools import reduce from collections import deque, defaultdict sys.stdin = open("input.txt", "rt") sys.setrecursionlimit(1501*1501) N, M, T = map(int, input().split()) board = [[0]*M for _ in range(N+1)] for i in range(N): board[i+1] = deque(list(map(int, input().split()))) for _ in range(T): x, d.. 더보기
[Python][백준 1405번] 미친로봇 # https://www.acmicpc.net/problem/1405 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # 각 가는 경로마다, check 배열 세팅 # path 개념으로, 만약, N 만큼 이동할시 # 해당 path 에 대한 확률을 계산한다. num, E, W, S, N = map(int, input().split()) probs = [float(N/100), float(S/100), float(W/100), float(E/100)] check = [[False]*30 for _ in range(30)] tPaths = 0 def findPath(path, number, x, y): global check, tPaths if number == num: tPaths += p.. 더보기
[C++][백준 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][백준 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][백준 11404번] 플로이드 # https://www.acmicpc.net/problem/11404 import sys import heapq from copy import deepcopy from collections import Counter , deque, defaultdict # 모든 점에서, 다른 모든점까지의 최소 거리 = 플로이드 와샬 n = int(input()) m = int(input()) INT_MAX = int(1e9) dp = [[INT_MAX] * n for _ in range(n)] # 자기 자신으로의 거리 0 for i in range(n): dp[i][i] = 0 for _ in range(m): st,ed,cst = map(int,input().split()) st,ed = st-1,ed-1 if cs.. 더보기
[Python][백준 10830번] 행렬곱셉 # https://www.acmicpc.net/problem/10830 from copy import deepcopy N,B = map(int,input().split()) f_matrix = [list(map(int,input().split())) for _ in range(N)] c_matrix = deepcopy(f_matrix) divided = [] # 시간초과 방지를 위해, 반반씩 곱해가는 원리를 적용해갈 것이다 # 예를 들어, B가 8이라면, 8번 행렬을 곱하는 것이 아니라 # A^1, A^2, A^4, A^8 이런 식으로 곱하는 단계를 간소화 할 것이다 tmp = B # 2로 나눈 몫들을 구해간다 while tmp >= 1 : divided.append(tmp) tmp = tmp // 2 .. 더보기

티스토리툴바