문제 11057 - 오르막 수 접근 DP 문제이다. 오르막수가 되기 위해선 자신 앞자리의 숫자보다 크거나 같아야한다. 이를 통해 DP를 구상하면 된다. 나는 DP를 자릿수와 각 자리마다 0~9까지로 하여 10개로 구성했다. DP(i, j) = i번째 자리에 j가 들어왔을 때 가능한 경우의 수이다. DP(2, 3) = 2번째 자리가...

문제 1922 - 네트워크 연결 접근 최소 스패닝 트리 문제이다. 그래프에서 최소 비용을 사용하여 트리 구조를 만든다고 생각하면 된다. 그래프 표현은 인접 리스트 방식을 사용했고, 프림 알고리즘을 이용하여 해결했다. 방문 여부를 나타내는 배열하나와 현재까지 방문한 노드들 중 다음 노드와 연결하기 위한 최소 비용을 찾기 위해 우선순위 큐를...

문제 1182 - 부분 수열의 합 접근 보통 원하는 수를 만들거나 초과하면 거기서 멈추지만, 이 문제의 경우 음수도 포함되어 있기때문에 끝까지 돌려봐야한다. 코드 파이썬 코드 def func(idx, nowSum): if n == idx: if s == nowSum: return ...

문제 1158 - 요세푸스 문제 접근 문제 자체는 간단하다. 한 사람씩 제거하면서 움직여야하는데 인덱스 관리를 어떻게 해주느냐가 관건이다. 코드 파이썬 코드 n, k = map(int, input().split()) result = [] n = [i+1 for i in range(n)] nowLoc = 0 while n...

문제 4597 - 패리티 접근 1의 개수와 마지막 글자가 e, o 여부에 따라 답이 달라진다. 현재 1이 짝수개인지, 홀수개인지 그리고 e인지 o인지 조합하여 4가지 경우에 대해 조건을 주면 된다. 코드 파이썬 코드 while True: bitString = input() if bitString == '#'...

문제 13458 - 시험 감독 접근 시험장당 총 감독관 한명은 고정이다. 그리고 남은 학생을 감당할 수 있는만큼 부 감독관을 넣으면 된다. 코드 파이썬 코드 n = int(input()) arr = list(map(int, input().split(' '))) mainS, subS = map(int, input().spli...

문제 13301 - 타일 장식물 접근 DP 문제이다. 타일의 크기는 피보나치 수열과 같다. 타일의 크기에 대한 배열을 n 이라고 하자. 둘레에 대한 배열은 size 라고 하자. n에 대한 dp는 피보나치와 마찬가지로 n[i] = n[i-1] + n[i-2] 이다. 둘레의 경우 size[i] = size[i-1] + 2n[i] 이다....

문제 15953 - 상금 헌터 접근 주어진 조건으로 상금을 알아내면 된다. 주의할 것은 등수는 누적해야 한다. 코드 파이썬 코드 t = int(input()) def fastival1(score): if score == 1: return 5000000 elif 1 < score <...

문제 1085 - 직사각형에서 탈출 접근 상하좌우 가장 가까운 곳을 찾으면 된다. 코드 파이썬 코드 x, y, w, h = map(int, input().split(' ')) print(min(x, w-x, y, h-y))

문제 1284 - 집 주소 접근 1, 0 인 경우만 따로 처리해주면 된다. 코드 파이썬 코드 while True: num = list(map(int, list(input()))) if len(num) == 1 and num[0] == 0: break ans = 1 + len(num) ...