문제 손해를 보지 않으면서 채굴할 수 있는 가장 많은 금의 개수를 출력하는 문제이다. 풀이 해당 문제에서 마름모의 모양을 결정할 때 중심으로부터 K만큼까지 떨어질 수 있는 것을 정의로 한다. 이 때 마름모의 중앙과 K가 주어졌을 때 임의의 좌표가 마름모 내부에 있는지 확인하는 코드는 다음과 같다. def getNumOfGold(row, col, k): return sum([ matrix[i][j] for i in range(n) for j in range(n) if abs(row - i) + abs(col - j) = getArea(k): maxGold = max(maxGold, numOfGold) 이 후 금을 얻었을 때 손해인지 계산한 후 기존 maxGold와 비교하면 된다. 이 때 getArea는..
https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 주어진 문자열에서 특정 문자를 지운 후의 결과를 출력하는 문제이다. 풀이 스택을 이용하여 해결하였다. word = list(input()) explode = list(input()) explodeLen = len(explode) 먼저 문자열과 지울 문자, 그리고 지울 문자의 길이를 초기화하였다. for i in word: q.append(i) if q[len(q) - ex..
https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제 주어진 트리의 한 부분을 제거했을 때, 해당 트리의 리프노드의 개수를 출력하는 문제이다. 풀이 노드의 리프노드를 확인하는 문제이므로 DFS를 사용하였다. N = int(input()) node = list(map(int, input().split())) delete = int(input()) 먼저 노드의 정보와 지울 노드의 번호를 입력받는다. def DFS(num, arr): arr..
2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 주어진 타일을 이용해서 타일을 완성시키는 경우의 수를 출력하는 문제이다. 풀이 먼저 타일을 배치할 수 있는 경우의 수를 구해야한다. n이 홀수일 경우 타일을 배치할 칸이 부족하므로 경우의 수가 0이된다. n = 2 의 경우는 다음과 같다. n = 4 의 경우 고유한 모양 2개 + n = 2일 때의 모양의 조합 9가지 = 11가지가 된다. n = 6 의 경우 끝부분의 n이 2, 4, 6인 경우를 모두 더해주면 된다. 이 때 6인경우는 고유패턴 2가지이므로 2를 더해주면 된다. 이런식으로 짝수의 경우를 모두 표현할 수 있다. 해당 식을 그림으로 나타내면 다음과 같다...
2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 문제 주어진 동전의 종류를 이용해 최소한의 개수로 원하는 숫자를 만드는 문제이다. 풀이 Dp배열을 생성 후 N의 숫자를 만들 때 필요한 동전의 최소값을 Dp[N]에 저장하는 방법을 사용하여 해결하였다. coin = [] for i in range(n): coin.append(int(input())) dp = [sys.maxsize] * (k + 1) dp[0] = 0 동전의 종류를 입력받고 dp배열을 초기화한다. 이 때 0을..
https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 공간과 아기상어, 먹이가 주어질 때 아기상어가 물고기를 잡아먹을 수 있는 최단시간을 구하는 문제이다. 풀이 먼저 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러간다. 라는 조건이 있다. 따라서 BFS를 사용하는데 이는 BFS가 최단경로를 가지기 때문이다. 이를 해결하기 위해 다음과 같은 순서를 사용하였다. 1. BFS를 사용하여 현재 위치에서 각 위치..