chldkato

https://www.acmicpc.net/problem/1793 1793번: 타일링 문제 2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. 출력 입력으로 주어지는 각각의 n마다, 2×n 직사각형을 채우는 방법의 수를 출력한다. 예제 입력 1 복사 2 8 12 100 200 예제 출력 1 복사 3 171 www.acmicpc.net 한 칸을 채우는 방법은 세로로 타일을 배치하는 방법 하나 두 칸을 채우는 방법은 가로로 타일을 2개 배치하는 방법과 2x2 타일을 배치하는 방..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. www.acmicpc.net 한 칸을 채우는 방법은 세로로 타일을 배치하는 방법 하나 두 칸을 채우는 방법은 가로로 2개로 배치하는 방법과 2x2 타일을 배치하는 방법 2개 따라서 a[i] = a[i-1] + 2 * a[i-2] import sys input = sys.stdin.readline n = int(input()) if n == 1: print(1) sys.exit() a = [0 for _ in range(n+1)] a[0], a[1] = 1, 1 for i in range(2, n+1): a[i] ..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net *** | *** | 한 칸을 채우는 방법은 위의 방법밖에 없다 ** ㅡ ** ㅡ 두 칸을 채우는 방법도 한 가지뿐 따라서 a[i] = a[i-1] + a[i-2] import sys input = sys.stdin.readline n = int(input()) if n == 1: print(1) sys.exit() a = [[] for _ in range(n+1)] a[0], a[1] = 1, 1 for i in r..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지 www.acmicpc.net dfs + dp로 목적지까지 도착할 수 있는지 검사한다 루프를 방지하기 위해 방문 확인 배열 c를 -1로 초기화하고 이동할 때마다 0으..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net n이 1인 경우와 2인 경우를 기본값으로 설정해둔다 3부터는 다음 세가지 경우 중 최대값으로 설정 1. 세번째 포도주를 마시지 않는경..

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계 www.acmicpc.net 1. disjoint-set으로 입력의 왼쪽을 부모로 하는 집합을 만들어준다 2. union에서 부모를 설정할 때 네트워크의 크기도..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 www.acmicpc.net 플로이드-와샬로 모든 경로를 구해놓고 여행 경로가 가능한지 출력 import sys INF = sys.maxsize input = sy..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a www.acmicpc.net 1. 집합 n+1개를 만들고 자기자신을 부모로 설정한다 2. z가 0이면 앞의 숫자를 부모로 하는 disjoint-set 실행 3. ..