투투

문제 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 접근 수들의 규칙성을 찾으려고 하였다. 4는 7가지의 경우의 수가 있었는데 1은 1, 2는 2, 3은 4의 경우의 수가 있었고 각 경우의 수를 펼쳤을 때 중복되는 연산이 많았다. 따라서 현재 N의 경우의 수는 N-1, N-2, N-3일 때의 경우의 수와 같다는 것을 알게되었다. 구현 먼저 1, 2, 3일 때를 먼저 구해놓고 이후의 수들은 for문을 통해 idx..

문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. ..

문제 이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다. 아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다. 입력 첫째 줄에 테스트 케이스가 입력된다. 테스트 케이스마다 한 줄에 하나씩 K와 N을 입력한다. K와 N은 1이상 14이하이다. 출력 K층 N호에 몇 명이 사는지 출력한다. 접근 처음에 문제가 잘 이해되지 않았다. 그래서 그림을 그려보면서 ..

www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 접근 1은 1칸 2~7은 2칸 8~19는 3칸 20~37은 4칸 이렇게 나열하여 규칙을 찾아보면 1 -> 7 -> 19 -> 37 에서 각 수가 증가하는 크기가 6 -> 12 ->18 이다. 따라서 처음에 1에서 6을 더하고 그 다음 12를 더하는 식으로 나아가서 찾아가야 할 칸이 그 범위에 속하면 몇 칸인지 출력한다. 구현 찾아야할 칸을 N에 입력받는다. 그리고 idx는 초기 1번을 나타내며 현재 1번에서 1번까지는 ..

문제 손님이 도착하는 대로 빈 방을 배정하고 있다. 호텔 정문으로부터 걷는 거리가 가장 짧도록 방을 배정하는 프로그램을 작성하고자 한다. 호텔은 직사각형 모양이라고 가정하자. 각 층에 W개의 방이 잇는 h층 건물이다. 엘레베이터는 가장 왼쪽에 있다. 이런 형태의 호텔을 HxW 형태 호텔이라고 부른다. 호텔 정문은 1층 엘레베이터 바로 앞에 있다. 정문에서 엘레베이터까지의 거리는 무시하고 인접한 두방 사이의 거리는 모두 1이다. 방 번호는 YXX 또는 YYXX형태이며 Y나 YY는 층 수 XX는 엘리베이터에서부터 세웠을 때의 번호를 나타낸다. 손님은 엘레베이터를 타고 이동하는 거리는 신경쓰지 않는다. 다만 걷는 거리가 같을 때에는 아래층의 방을 더 선호한다. 초기에는 모든 방이 비어있고 N번째로 도착한 손님..

문제 (x, y)에 위치해 있을 때 왼쪽 아래 꼭짓점 (0, 0) - 오른쪽 위 꼭짓점 (w, h)를 갖는 직사각형에서 경계선까지 가는 거리의 최솟값을 구하라 입력 첫째 줄에 x, y, w, h가 입력된다. w, h는 1이상 1000이하 출력 경계선까지의 최소거리를 출력한다. 접근 (x, y)에서 상하좌우의 거리만 구해보면된다. 따라서 최솟값의 후보가 될 수 있는 것은 x와 y값 그리고 w-x, h-y가 된다. 구현 min함수를 활용하여 위에서 봤던 네 개의 값을 비교하였다. x, y, w, h = map(int, input().split()) answer = min(x, min(y, min(w-x, h-y))) print(answer)

문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 접근 2차원 리스트에 무방향 그래프를 표현하고 DFS를 탐색하여 연결 요소들을 찾는다. 이때 DFS가 실행된 수만큼 연결 요소의 수가 된다. 구현 정점과 간선을 입력받고 정점의 크기만큼 2차원 리스트를 생성한다. 그리고 방문표시를 위한 1차원 리스트도 생성한다. -> False로 초기화됨 N, M = map(int, input().split()) matrix = [[0 for _ in range(N)] for..

문제 피보나치 함수를 실행했을 때 0일 때와 1일 때 몇 번 실행되는지 구하라 입력 첫째 줄에 테스트 케이스가 주어지며 이어서 40이하의 수가 입력된다. 출력 테스트 케이스마다 0일 때와 1일 때 실행횟수를 공백을 두고 출력한다. 접근 처음에 재귀함수를 사용해서 풀었는데 시간초과가 발생했다. 그래서 DP에 분류가 되어있던 것 같다 DP로 접근을 했을 때 각 수에서 0과 1이 몇 번실행되는지 규칙을 찾았을 때 현재인덱스 idx에서 idx-1, idx-2의 0과 1을 누적합을 해주면 된다. 구현 테스트 케이스마다 수를 입력받고 dp를 저장할 2차원 리스트를 생성한다. 그리고 초기에 0과 1에서는 0과 1이 몇 번 실행되는지 저장해둔다. N = int(input()) dp = [[0, 0] for _ in r..

www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 이 문제는 그림을 참고해야한다. 위에서 아래로 규칙을 통해 수를 선택해 더했을 때 맨 밑에서 최댓값을 찾는 것이다. 접근 백준의 RGB거리와 유사한 방법이다. 위에서 아래로 내려올 때 최댓값을 더해주면서 내려오도록 한다. 이러한 문제도 삼각형의 높이를 줄이면서 어떤 규칙이 있는지 찾아야한다. 구현 정수 삼각형의 정보를 2차원 리스트인 samgak에 저장을 한다. y는 층수, x는 해당 층의 정수의 자리를 나타내는데 0번째의 수는 이전의 0과 더하고 끝자리는 이전의 끝자리 이전을 더한..

문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 접근 타일의 크기가 커질수록 이전 크기의 타일에 몇개만 추가해주면 그 크기가 된다. 따라서 동적계획법이 쉽게 생각날 수 있었다. 지금의 타일의 개수가 다음 크기의 타일 개수에 영향을 미친다. 구현 현재 크기는 전과 전전의 타일의 개수를 더한 것과 같다. 따라서 dp[i-1] + dp[i-2]로 점화식을 세워 풀어줬다. import sys input = sys.stdin.read..