본문 바로가기

파이썬22

[python] 구름이의 여행 문제 구름이가 사는 나라는 N개의 섬으로 이루어져 있다. 각 섬에는 1부터 N까지의 번호가 붙어 있고, 각 섬마다 편하게 이동할 수 있도록 다리를 M개 설치했다. 설치된 다리들은 아래 특징들을 만족한다. 모든 다리는 양방향으로 이동할 수 있다. 서로 다른 두 섬을 잇는 다리는 최대 하나이다. 다리가 잇는 두 섬은 항상 다른 섬이다. 구름이는 1번 섬에서 출발해서 N번 섬으로 가려고 하는데, 통과하는 다리의 개수가 K개 이하가 되길 원한다. 구름이를 도와 1번 섬에서 N번 섬까지 K개 이하의 다리를 이용해 도착할 수 있는지를 판별해보자. 입력 첫째 줄에 섬의 개수 N과 다리의 개수 M, 그리고 구름이가 건널 다리의 최대 개수 K가 공백을 두고 주어진다. 다음 M개의 줄에는 다리가 잇는 두 섬의 번호를 의미.. 2023. 6. 21.
[python] 보드 게임 문제 어느 보드 게임은 0번 칸부터 N번 칸까지 N+1 개의 칸이 일렬로 놓인 보드와 말 하나로 구성되어 있다. 처음에는 시작 지점인 0번 칸에 말을 두고, 말을 도착 지점인 N번 칸까지 옮기는 것이 게임의 목표이다. 말을 옮길 때는 다음 규칙을 따라야 한다. 말을 한 번 옮길 때 항상 1칸 또는 3칸 앞으로만 옮길 수 있으며, 보드 밖으로 말을 옮길 수는 없다. 해당 규칙에 따라서 시작 지점에서 도착 지점까지 말을 옮길 수 있는 방법의 개수를 출력하시오. 단, 값이 너무 커질 수 있으니 1,000,000,007로 나눈 나머지를 출력하시오. 입력 첫째 줄에 N이 주어진다. 1 ≤ N ≤ 100,000 import sys input = sys.stdin.readline n = int(input()) boa.. 2023. 6. 20.
[python] 피보나치 수 문제 피보나치 수열에 포함되는 수를 피보나치 수라고 한다. 피보나치 수열은 첫째 항과 둘째 항이 1이고, 그 뒤의 모든 항은 바로 앞 두 항의 합으로 정의되는 수열이다. Fi를 i번째 피보나치 수라고 했을 때, 피보나치 수열을 수식으로 정의하면 아래와 같다. 양의 정수 K가 주어질 때, Fk의 값을 구해보자. 단, 값이 매우 클 수 있으니 이를 1,000,000,007로 나눈 나머지를 대신 출력한다. 입력 첫째 줄에 양의 정수 K가 주어진다. 1 ≤ K ≤ 100,000 import sys input = sys.stdin.readline k = int(input()) result = [1, 1] for i in range(2, k): result[0], result[1] = result[1], resul.. 2023. 6. 20.
[python] 직사각형 만들기 문제 N개의 막대기 중 일부를 잘 배치해서 직사각형을 만들고자 한다. 직사각형을 만들기 위해서는 길이가 같은 막대기 두 쌍이 필요하다. 같은 쌍에 속한 막대기들을 마주 보게 배치하고, 다른 쌍에 속한 막대기들을 수직으로 배치하면 직사각형을 만들 수 있다. 길이가 a인 막대기와 길이가 b인 막대기 쌍을 사용해서 직사각형을 만들었을 때, 만들어진 직사각형의 넓이는 ab이다. 하나의 막대기는 하나의 직사각형을 만드는 데만 이용할 수 있고, 가능한 많은 직사각형을 만들면서도 직사각형들의 넓이 합이 최대가 되고자 한다. 가지고 있는 막대기의 정보가 주어졌을 때, 만들 수 있는 직사각형들의 넓이 합의 최댓값을 구하시오. 입력 첫째 줄에는 가지고 있는 막대기의 개수 N이 주어진다. 둘째 줄에는 S1, ..., Sn .. 2023. 6. 19.

티스토리툴바