흙금이네 블로그

아이디어 BFS로 건물 내부와 외부를 구분한 후, 외부에 보이는 벽면의 수를 구한다. 풀이 #1 (Python) 문제의 정육각형 좌표 값 y가 홀수일 때를(인덱스 기준 짝수) 기준으로 위치 변화 값들을 튜플로 리스트 delta에 저장한다. 지도의 너비 W, 지도의 높이 H를 입력 받고, 집의 건물 배치를 2차원 리스트 buildings에 저장한다. 지도 가장자리 부분의 좌표들을 인자로 함수 bfs를 호출하여 건물 내부와 외부를 구분한다. 인덱스가 홀수인 행이면서 행의 위치가 변하면 delta에서 열 변화 값을 1을 감소시켜 위치 변화 값을 조정한다. 함수 bfs 호출로 지도 buildings에서 외부 공간은 -1, 내부 공간에서 건물이 있는 곳은 1, 없는 곳은 0의 값을 갖게 된다. 이후 건물이 있는 ..

아이디어 BFS로 1번 헛간과 거리가 가장 먼 헛간들을 찾는다. 풀이 #1 (Python) 방문 표시 및 1번 헛간과의 거리를 저장하기 위해 N+1 크기의 0으로 채워진 리스트 visited를 생성한다. visited에서 1번 헛간의 값을 1로 저장하고, 큐 queue에 1을 저장한다. while문에서 BFS로 방문하지 않은 주변 헛간으로 이동하며 visted에 1번 헛간과의 거리보다 1 더 큰 값을 저장한다. 모든 헛간을 방문한 후 for문에서 숨어야 하는 헛간 번호 num, 해당 헛간까지의 거리 d, 같은 거리의 헛간 수 cnt를 구한다. import sys input = sys.stdin.readline def solution(): N, M = map(int, input().split()) grap..

아이디어 BFS로 나이트가 체스판의 각 칸에 방문하기 위한 최소 이동 횟수를 구한다. 풀이 #1 (Python) 나이트가 이동할 수 있는 위치의 변화 값을 튜플로 리스트 delta에 저장한다. 체스판 내 각 칸의 최소 이동 횟수를 저장하기 위해 (N+1)×(N+1) 크기의 0으로 채워진 2차원 리스트 visited를 생성한다. visited에서 나이트의 초기 위치를 1로 저장하고, 큐 queue에 나이트의 초기 위치를 저장한다. while문에서 BFS로 나이트가 이동할 수 있는 칸으로 이동하며 visted에 최소 이동 횟수를 저장해 나간다. 체스판의 모든 칸에 대해 최소 이동 횟수를 저장한 후, for문에서 상대편 말을 잡기 위한 최소 이동 횟수들을 출력한다. import sys input = sys.s..

아이디어 BFS로 칸을 이동하며 게임을 클리어할 수 있는지 확인한다. 풀이 #1 (Python) 지도 정보를 lines에 입력 받고, 큐 queue에 칸 인덱스, 줄 인덱스, 시간이 모두 0인 튜플을 초기값으로 저장한다. while문에서 queue에 저장된 튜플을 차례로 꺼내 i, j, t에 저장한다. 반대편 줄의 i+k번 칸으로 이동해 게임을 클리어할 수 있다면 결과값 res에 1을 저장하고 break로 while문을 종료한다. 게임을 클리어할 수 없다면 i+k번 이하의 칸(k는 1 이상이므로 최소 i+1번 칸)은 유효하다. 따라서 반대편 줄의 i+k번 칸, i+1번 칸이 안전하면 queue에 추가하고, i-1번 칸은 안전한 칸이면서 이번 차례에 사라지지 않으면 queue에 추가한다. queue에 추가..

아이디어 만들 수 있는 2진 수열 개수의 규칙을 찾는다. 풀이 #1 만들 수 있는 2진 수열은 타일 개수에 따라 피보나치 수열을 이루고 있다. res와 prev에 각각 현재와 이전 피보나치 수 저장하여 계산하고, res를 15,746으로 나눈 나머지를 출력한다. def solution(): N = int(input()) prev = res = 1 for i in range(2, N+1): res, prev = (res+prev)%15746, res print(res) solution() 풀이 #2 행렬 곱을 이용하여 피보나치 수열을 빠르게 구할 수 있다. 2차원 행렬을 1차원 튜플로 표현하고, N을 이루는 2의 제곱수마다 해당하는 거듭제곱 행렬을 곱한다. def fibo(a, b): return ((a[..

아이디어 돌 개수에 따른 결과의 규칙을 찾는다. 풀이 돌 개수가 홀수면 상근이가, 짝수면 창영이가 게임을 이기게 된다. print('SK' if int(input())%2 else 'CY')

아이디어 규칙을 찾고 동적 계획법으로 가짓수를 계산한다. 풀이 고정석으로 구분된 연속된 좌석에 대해 그 가짓수가 좌석 개수에 따라 피보나치 수열을 이루고 있다. 리스트 vip에는 0과 좌석 끝 번호를 추가하여 고정석 번호를 저장하고, 리스트 dp에는 피보나치 수열을 저장한다. 전체 가짓수는 연속된 일반 좌석들의 곱이므로 결과값 res에 일반 좌석 개수에 따른 피보나치 수열의 수를 곱한다. import sys input = sys.stdin.readline def solution(): N = int(input()) M = int(input()) vip = [0]+[int(input()) for _ in range(M)]+[N+1] dp = [1]*(N+1) for i in range(2, N+1): dp[..

아이디어 동적 계획법으로 각 블록을 사용하여 탑을 만드는 경우의 수를 구해 나간다. 풀이 #1 (Python) 2624번 동전 바꿔주기 문제 풀이와 유사하다. 0으로 채워진 H+1 크기의 리스트 dp를 생성하는데, dp[i]에는 높이 i의 탑을 만드는 경우의 수를 저장한다. for문에서 리스트 blocks에 블록들의 높이를 입력 받고, temp에 리스트 dp를 복사하여 저장한다. blocks의 블록 하나로 해당 블록의 높이만큼 탑을 쌓는 경우의 수 dp[b]를 1 증가시키고, 해당 블록을 기존 블록들을 함께 사용해 탑을 쌓아 높이 i의 탑을 경우의 수를 temp[i-b]만큼 증가시킨다. 높이 H의 탑을 쌓는 경우의 수를 10,007로 나눈 나머지를 출력한다. import sys input = sys.st..

아이디어 동적 계획법으로 각 동전을 사용한 교환 방법의 가짓수를 저장해 나간다. 풀이 #1 (Python) 0으로 채워진 T+1 크기의 리스트 dp를 생성하는데, dp[i]에는 i원의 교환 방법 가짓수를 저장한다. for문에서 동전의 금액 p와 동전 개수 n을 입력 받고, temp에 리스트 dp를 복사하여 저장한다. p원 동전으로만 교환하는 방법의 가짓수는 1이므로 n 이하의 자연수 i에 대해 dp[p*i]를 1씩 증가시킨다. p원 동전을 사용하여 교환하는 방법의 수는 그 금액보다 p원만큼 작은 금액을 기존 동전들로 교환하는 방법의 수와 같다. 따라서 기존 동전들과 함께 사용하여 교환하는 방법의 수 dp[j]에 기존 동전들로만 교환하는 방법의 수 dp[j-p*i]를 더한다. 지폐의 금액 T를 넘는 동전의..

아이디어 동적 계획법으로 감소하는 수열 합의 최댓값을 구한다. 풀이 #1 (Python) 리스트 dp에 수열 A와 같은 값들을 저장한다. 이중 for문에서 수열의 두 요소를 비교하여 수가 감소할 때 더 큰 부분 수열의 합으로 갱신해 나간다. max(dp)로 전체 감소 부분 수열의 합 중 가장 큰 값을 찾아 출력한다. def solution(): N = int(input()) A = tuple(map(int, input().split())) dp = list(A) for i in range(N): for j in range(i+1, N): if A[j] dp[j]: dp[j] = dp[i]+A[j] print(max(dp)) solution() 풀이 #2 (Jav..