expresshighway

import sys from collections import deque input = sys.stdin.readline count = 0 h, w = map(int, input().split()) visited = [[False]*w for _ in range(h)] dia = [input().split() for i in range(int(h))] dx = (-1, 0, 1, 0) dy = (0, 1, 0, -1) def bfs(i, j): queue = deque() queue.append((i, j, 0)) visited[i][j] = True num = 0 while queue: x, y, distance = queue.popleft() for k in range(4): nx, ny = x+dx..

import sys from collections import deque input = sys.stdin.readline count = 0 h, w = map(int, input().split()) visited = [[False]*w for _ in range(h)] dia = [input().split() for i in range(int(h))] dx = (-1, 0, 1, 0) dy = (0, 1, 0, -1) def bfs(i, j): queue = deque() queue.append((i, j, 0)) visited[i][j] = True num = 0 while queue: x, y, distance = queue.popleft() for k in range(4): nx, ny = x+dx..

import sys from collections import deque input = sys.stdin.readline def bfs(node, number): queue = deque() queue.append((node, number)) while queue: node, number = queue.popleft() for n in [node+1, node*2, node*3]: if n

import sys from collections import deque, defaultdict input = sys.stdin.readline number = list(map(int, input().split())) visited = defaultdict(bool) total = sum(number) def dfs(): queue = deque([number]) visited[tuple(number)] = True while queue: A, B, C = queue.popleft() if A == B == C: return 1 for x, y in ((A, B), (B, C), (A, C)): if x == y: continue elif x < y: y = y-x x = x*2 else: x = x-y..

문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입력 5 3 1 2 8 4 9 출력 3 소스코드 bisect_index import sys N, C = map(int, input().split()) house = [int(sys.stdin.rea..

정말 DP에 소질이 없는 나는 DP 문제를 많이 풀어야 할 것 같다... 왜 어떻게 접근해야겠다는 생각조차 못할까? 일단 하나 하나 적어보자 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) 입력 예제 2 출력 예제 17 문제 풀이법 첫번째, 자리수가 1일 때를 보자 자리수/ 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 1 1 1 1 1 1 2 3 두번째, 자리수 2일 때를 쌓아보자 자리수/ 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 1 1..

문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 3 26 40 83 49 60 57 13 89 99 출력 96 원래 dp 새로운 배열을 만들어서 넣어야 하지만 입력 배열에 덮어써주면 메모리를 많이 사용할 필요 없을 것 같다. 조건이 굉장히 길지만 인접한 것이..

내 머리에서 이해가 가서 행복하게 리뷰를 해본다. 호호호호 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 3 10 1 2 5 출력 10 1로 k를 만드는 경우 1만 사용하여 만들 수 있음! 세로는 동전의 종류이고, 가로는 k이다. k는 입력하는 값이기 때문에 1부터 차례 차례 구해나가야 한다. 1 2 3 4 5 6 1 1 1 1 1 1 1 2 5 결과 1로 1을 만들 수 있는 경우의 수: 1개 1로 2를 만들 수 있는 경우의 수: 1개 (1+1) 1로 3을 만들 수 있는..

문제 오늘 사탕 M개를 가득 담은 박스가 택배로 택희네 집에 도착했다. 택희는 이 사탕을 N명의 친구들에게 나누어 주려고 한다. 택희의 친구들은 문자로 사탕을 몇 개 받고 싶은지 보냈다. 만약 받고 싶은 개수만큼 사탕을 받지 못한다면, 그 친구는 분노하게 되고, 못 받는 개수가 많아질 수록 더욱 분노하게 된다. 놀랍게도 택희는 친구들의 분노를 수치화 할 수 있는데, 이것은 못 받는 사탕 개수의 제곱이다. 예를 들어, 택희의 친구 백준이가 받고 싶은 사탕의 개수가 32개였을 때, 사탕을 29개 받아 3개를 받지 못한다면, 그의 분노는 3의 제곱 9가 된다. 택희가 받은 사탕의 개수와 친구의 수, 그리고 그 친구들이 받고 싶어하는 사탕의 개수가 주어졌을 때, 사탕을 적절히 나누어 주어 친구들의 분노의 합을 ..

문제 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오. 입력 2 5 ..