조준장 개발자 생존기

문제 14247번: 나무 자르기 영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 www.acmicpc.net 알고리즘 - 문제를 해석해보면 모든 나무를 한 번씩 자르는 게 최대 나무 양을 구하는 방법인 것을 알 수 있다. - 나무의 초기 값과 나무가 자라는 수치를 2차원 리스트로 만들어 나무가 자라는 수치를 기준으로 오름차순 정렬한다. - 나무가 자라는 수치가 작은 나무부터 자른다. - 나무의 초기값과 나무가 자라는 수치 x 현재 날짜를 더한 값을 모두 더해 출력한다. - 위 방법보다 더 효율적인 방법으로는 아래 설명에 있다. 코드 (42976KB/120ms) im..

문제 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 알고리즘 - 반복문을 통해 바둑알이 있는 위치를 탐색한다. - 우/ 아래/ 대각선 우 우 아래/ 대각선 우 위 => 4가지 방향으로 탐색한다. - 위에서부터 오른쪽으로 탐색하기 때문에 왼/위/아래 왼 아래/ 아래 왼 위 방향은 탐색할 필요 없다. - 4가지 방향으로 탐색하면서 오목이 되는지 확인한다. - 오목이 되는지 확인하는 방법으로는 이전에 이동했던 방향으로 5번 이동했을 때 매번 같은 바둑알의 색인지 확인하는 것이다. - 이때 시작 점의 뒷 방향에 바..

문제 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 알고리즘 - 반복문을 통해 종이를 확인한다. - 시작점에 종이의 수가 현재 종이의 수와 다르다면 3* 3 범위를 재귀적으로 탐색한다. - 탐색할 때 3으로 나눈 범위를 그 종이의 수 x, y 좌표를 탐색한다. - 탐색이 모두 끝난 구역은 카운트한다. 코드 import sys def dfs(x, y, z): global answer visited = graph[x][y] # 반복문을 통해 종이를 확인 for i in range(x, x + z): ..

문제 1986번: 체스 첫째 줄에는 체스 판의 크기 n과 m이 주어진다. (1 ≤ n, m ≤ 1000) 그리고 둘째 줄에는 Queen의 개수와 그 개수만큼의 Queen의 위치가 입력된다. 그리고 마찬가지로 셋째 줄에는 Knight의 개수와 위치, www.acmicpc.net 알고리즘 - queen과 knight가 이동할 수 있는 곳을 dfs로 탐색한다. - knight의 경우 한 번만 이동해야 되므로 한 번만 탐색하게끔 한다. - 반복문을 통해 모든 좌표를 탐색 후 queen과 knight가 이동할 수 없는 좌표의 개수를 출력한다. 코드 import sys sys.setrecursionlimit(10**9) # queen을 dfs 탐색 def dfs_queen(x, y, v): if x < 0 or x..

문제 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 알고리즘 - 반복문을 통해 갈 수 있는 그래프의 좌표를 탐색한다 - 현재 탐색하는 좌표가 오른쪽 아래 맨 끝 점이면 반복을 멈추고 오른쪽 아래 맨 끝 점까지 이동 가능한 개수를 출력한다. - 오른쪽과 아래로 이동할 수 있다면 이동하고 그전 좌표까지 이동 가능한 값을 더한다. 코드 import sys n = int(sys.stdin.readline()) graph = [list(map(int, sys.stdin.readline().split()))..

문제 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 알고리즘 - 반복문을 통해 추천을 확인한다. - defaultedict 메서드를 이용하여 추천을 받는다. - 추천받은 사람의 수가 사진틀보다 크다면 추천받은 사람의 사진 중에서 하나를 삭제한다. - 반복문을 통해 추천받은 사람을 확인한다. - 추천받은 사람이 이번에 추천받은 사람이라면 무조건 사진틀에 들어가야 하기 때문에 넘긴다. - 추천받은 횟수가 제일 적은 사람을 찾아 삭제한다. - 추천을 모두 확인했다면 사진틀에 있는 사람을 학생 번호로 오름..

문제 1706번: 크로스워드 동혁이는 크로스워드 퍼즐을 좋아한다. R×C 크기의 크로스워드 퍼즐을 생각해 보자. 이 퍼즐은 R×C 크기의 표로 이루어지는데, 퍼즐을 다 풀면 금지된 칸을 제외하고는 각 칸에 알파벳이 하나씩 www.acmicpc.net 알고리즘 - 반복문을 통해 가로와 세로로 연속되는 단어를 찾는다. - 찾는 방법의 알고리즘은 다음과 같다. - 반복문을 통해 가로, 세로의 문자를 확인한다. - 현재 문자가 '#'가 아니면 문자를 낱말에 더해준다. - 현재 문자가 # 이면서 낱말의 길이가 2 이상이라면 낱말 모음에 추가한다. - 현재 문자가 # 이면서 낱말의 길이가 2 미만이라면 필요 없는 낱말이므로 ""로 낱말을 초기화한다. - 가로, 세로 모든 낱말 모음을 구했으면 사전식 순으로 정렬 후..

문제 1421번: 나무꾼 이다솜 첫째 줄에 이다솜이 가지고 있는 나무의 개수 N과 나무를 자를 때 드는 비용 C와 나무 한 단위의 가격 W이 주어진다. 둘째 줄부터 총 N개의 줄에 이다솜이 가지고 잇는 나무의 길이가 한 줄에 하나 www.acmicpc.net 알고리즘 - 반복문을 통해 나무를 1부터 제일 긴 나무의 길이만큼 잘라본다. - 반복문을 통해 모든 나무를 확인한다. - 나무를 자른 후 개수와 남은 나무의 길이를 구한다. - 남은 나무의 길이가 있다면 자른 나무 수만큼 비용을 낸다. - 남은 나무의 길이가 없다면 자른 나무 수 -1 만큼 비용을 낸다. - 자른 나무를 판 후 이익이 나는지 확인한다. - 이익이 난다면 money에 이익을 더한다. - 모든 나무를 확인한 후에 money가 이익의 총합..

문제 1411번: 비슷한 단어 첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 한 줄에 하나씩 단어가 주어진다. 단어의 길이는 최대 50이고, N은 100보다 작거나 같은 자연수이다. 모든 단어의 길이는 같고, 중복 www.acmicpc.net 알고리즘 - 반복문을 통해 단어를 확인한다. - 단어를 확인하는 과정으로는 단어의 각 알파벳을 확인하며 알파벳과 수를 dic에 추가한다. - 현재 확인한 알파벳을 temp에 추가한다. - dic에는 각 알파벳과 수가 추가되어 있을 것이고 temp에는 알파벳을 숫자로 바꾼 값들이 있을 것이다. - temp와 반복문을 통해 같은 단어인지 확인하고 카운트한다. 코드 import sys n = int(sys.stdin.readline()) temp = [..

문제 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 반복문을 통해 건너야 하는 다리를 모두 탐색한다. - 2개의 반복문을 통해 현재 다리에서 앞으로 가는 경우와 뒤로 가는 경우를 나눠 탐색한다. - 탐색 중 탐색하지 않은 다리가 나타나면 건너야 하는 다리 리스트에 추가하고 그 다리까지 점프한 수를 초기화한다. - 그때 탐색한 다리가 b번 다리라면 그때 탐색한 다리까지 점프한 수를 출력한다. - 모든 다리를 탐색한 후에도 b번 다리를 가지 못했..