흙금이네 블로그

아이디어 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에 추가..

아이디어 동적 계획법으로 각 블록을 사용하여 탑을 만드는 경우의 수를 구해 나간다. 풀이 #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..

아이디어 동적 계획법으로 각 자릿수에서 줄어들지 않는 수의 개수를 구한다. 풀이 #1 (Python) 0으로 채운 65×10 크기의 2차원 리스트 dp를 생성한다. dp[i][j]는 줄어들지 않는 i 자릿수 중 j로 시작하는 수의 개수이고, dp[i]의 합은 줄어들지 않는 i+1 자릿수의 개수다. i 자릿수에서 0으로 시작하는 줄어들지 않는 수의 개수 dp[i][0]는 이전 자릿수에서 줄어들지 않는 수의 합 sum(dp[i-1])이고, j로 시작하는 수의 다음 숫자 값은 j 이상이므로 dp[i][j]는 j-1로 시작하는 수를 제외한 dp[i][j-1]-dp[i-1][j-1]이다. dp[65]까지 계산하면 이후 입력으로 주어지는 n 자릿수의 개수를 dp[n+1][0]으로 구할 수 있다. import sys..

아이디어 동적 계획법으로 고객 수에 따른 최소 비용을 계산한다. 풀이 #1 (Python) 0으로 채운 (N+1)×100 크기의 2차원 리스트 dp를 생성한다. dp[i][j]에는 i번 사람 차례에서 체력이 j일 때 얻을 수 있는 최대 기쁨을 저장한다. 이중 for문에서 체력이 0(인사를 한번도 하지 않은 경우)이거나 dp[i][j]에 저장된 값이 있을 때 현재 사람에게 인사한 후의 체력이 100 미만이면 인사한 후의 상태인 dp[i+1][j+L[i]]에 인사한 후의 기쁨을 저장하고, 인사하기 전과 비교해 인사하기 전의 기쁨이 더 크다면 dp[i+1][j]에 인사하기 전의 기쁨 dp[i][j]를 저장한다. import sys input = sys.stdin.readline N = int(input()) ..

아이디어 동적 계획법으로 고객 수에 따른 최소 비용을 계산한다. 풀이 #1 (Python) 고객 수에 필요한 최소 비용을 저장하는 C+1 크기의 리스트 dp를 생성하고, 초기값을 비용 최댓값 100,000으로 채운다. for문에서 홍보 비용과 그 고객 수를 a와 b에 입력 받고, 고객 i명을 얻는 데 필요한 최소 비용 dp[i]를 갱신해 나간다. b의 배수 이하의 고객을 얻는 비용을 그에 맞는 a의 배수와 비교해 더 작은 값으로 갱신한다. 또 고객 수 i에서 b만큼의 고객을 홍보 비용 a로 얻었을 때의 비용인 dp[i-b]+a와 비교해 더 작은 값으로 갱신한다. import sys input = sys.stdin.readline def solution(): C, N = map(int, input().sp..