투투

문제 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..

문제 N개의 계단을 규칙대로 올라서 마지막 계단을 밟는다. 한 번에 한 개, 두 개의 계단을 밟을 수 있으며 연속해서 세 개의 계단은 밟지 못한다. 시작점은 계단에 포함되지 않는다. 위의 규칙대로 마지막 계단을 밟았을 때 최댓값을 구하라. 입력 첫째 줄에 계단의 개수를 입력한다. 이어서 계단의 순서대로 계단을 밟았을 때 얻는 점수를 입력한다. 출력 계단을 다 올랐을 때의 최댓값을 출력한다. 접근 만약 5개의 계단이 있다고 했을 때 계단이 1개, 2개 있을 때의 최댓값을 구하였다. 즉 계단의 범위를 좁혀서 최댓값을 구하였고 이때 계단의 개수에 따라 경우의 수를 구했을 때 중복되는 인덱스들이 많았다. 따라서 이를 동적계획법으로 미리 저장해두고 좀 더 위에 있는 계단에서 이용하고자 하였다. 구현 계단에 대한 ..

문제 RGB 거리에 집이 N개 있다. 집은 1번부터 N번 집이 순서대로 있다. 이때 집의 색은 빨강, 초록, 파랑 중에 하나로 색칠을 해야하는데 옆에 같은 색깔의 집이 있을 수 없다. N개의 집을 모두 칠하는데 드는 최소비용을 구하라. 입력 집의 개수 N이 입력된다. (2이상 1000이하) 이후에 각 번호에서 R, G, B로 색칠할 때 드는 비용이 입력된다. 출력 N개의 집을 색칠하는데 드는 최소비용을 출력한다. 접근 N개의 집이 있을 때 집이 1개만 있을 때는 어떨지 나눠보았다. 그리디로 접근은 불가능했다. 현재 선택한 최소비용이 나중에 최소가 되지 않을 수 있었기 때문이다. 모든 경우의 수를 구한다고 했을 때 만약 1번 집을 R로 색칠하면 2번 집은 G, B 중에 하나로 색칠할 수 있는데 G B 중 ..

문제 2차원 방의 정보가 주어진다. " . "은 누울 수 있는 칸이고 "X"은 누울 수 없는 칸이다. 가로와 세로를 탐색해서 " . "이 2칸 이상 존재할 때 누울 수 있는데 가로와 세로 각각 몇 개의 누울자리가 있는지 구하라 입력 첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다. 출력 첫째 줄에 가로로 누울 수 있는 자리와 세로로 누울 수 있는 자리의 개수를 출력한다. 접근 가로와 세로를 각각 탐색하여 "."의 개수를 카운트한다. 카운트를 하다가 "X"를 만났을 때 그 동안 "."의 개수가 몇 개인지 파악하여 2이상이면 최종해를 증가시켜준다. 구현 아래는 가로..

문제 Nkg 그램의 설탕을 배달하려고 할 때 5kg, 3kg 박스에만 담아서 배달하려고 한다. 배달을 할 때 박스를 최소한으로 사용해서 배달을 해보자 입력 배달해야 할 설탕의 무게 N이 입력된다. 출력 몇 개의 박스가 필요한지 출력하고 5kg와 3kg의 박스로만 배달할 수 없을 때는 -1을 출력한다. 접근 최소한의 박스를 사용하기 위해서는 5짜리 박스를 많이 사용해야 한다. 5를 사용하기 위해서는 무게가 5와 나누어 떨어져야 한다. 따라서 5와 나누어 떨어지면 5에 모두 담고 그렇지 않는다면 설탕의 무게를 3씩 빼주도록 한다. 구현 while문 안에서 구현되며 무게 N이 0이상일 때만 실행된다. 처음에 N이 5와 나누어 떨어지면 바로 최종해에 5로 나눈 몫을 더해주고 끝낸다. 그렇지 않다면 -3을 해주고..

문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. 접근 처음에 버블정렬로 정렬하였다. 하지만 역시 시간초과가 발생하였다. 그렇기 때문에 sort함수를 사용였는데 sort 내부에 key값을 활용하였다. key값에 lambda로 어떠한 명령을 주면 그 값을 우선순위로 정렬이 된다. 위 ..

문제 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 출력 듣보잡의 수와 그 명단을 사전순으로 출력한다. 접근 두 개의 그룹에 모두 속한 이름을 출력하는 것이다. 집합으로 표현했을 때 교집합인 부분을 출력해야하며 파이썬에서 set()을 통해 집합을 표현한다. list 형의 그룹들을 set 형으로 변경하여 &..

문제 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다. 출력 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다. 접근 입력에서 주어진 정보로 그래프를 그리면 방향 그래프가 된다. 먼저 y축의 번호를 기준으로 탐색을 진행한다. 이때 방문 표시를 해서 무한루프가 돌지않도록 해야하는데 ..

문제 크기가 NxN의 각 칸에 R, G, B 색 정보가 담겨져있다. 적록색약인 사람은 R과 G를 구분하지 못하고 하나의 색으로 본다. 이때 각각의 색 구역을 적록색약이 아닌사람과 적록색약인 사람이 몇 개의 구역으로 보는지 구하라. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄부터 N개 줄에는 그림이 주어진다. 출력 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다. 접근 적록색약인 사람과 아닌 사람에 따라 다른 BFS로 하려고했지만 코드가 너무 길어졌다. 그래서 적록색약이 아닌 사람의 구역을 먼저 구한 다음에 그림판에서 G를 R로 바꿔주어 적록색약인 사람의 구역을 구하도록 하였다. 구현 그림판의 정보를 입력받는다. N =..

www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 접근 처음에 DFS로 탐색을 하여 관계의 합을 구하려고 했다. 하지만 스택을 이용해 풀면 관계의 합이 최소가 되지 않는다는 것을 알게되었다. 따라서 근접한 이웃 먼저 탐색을 하는 BFS로 풀어 통과가 되었다. 로직은 똑같은데 스택을 큐로만 바꿔주었다. 구현 사람의 수와 관계의 수를 입력받아 트리를 구성하였다. N, M = map(int, input().split(..