Algorithm

https://www.acmicpc.net/problem/2847 아이디어 예제 2를 예로 들면 5 3 7 5 레벨당 증가하는 점수가 각각 5, 3, 7, 5 이다. 1레벨을 통과하면 5점이 오르고 2레벨을 통과하면 3점이 오른다는 뜻이다. 하지만 1레벨이 2레벨보다 점수 증가폭이 크면 안된다!! 이전 레벨이 다음 레벨보다 점수 증가폭이 큰 경우 점수를 내려야한다. 문제 조건 중에 점수를 내리는 것을 최소한으로 해야한다고 적혀있다. 점수 내리는 것을 최소화 한다는 것은 이전 레벨이 다음 레벨보다 증가할 점수가 1만 차이나도록 점수를 내리는 것이 최소한으로 줄이는 것이다. 예를 들어 5 3 7 5면 4레벨이 5점인데 3레벨이 7점을 오른다고 했으므로 3레벨을 4로 만들어주면 된다. 3레벨이 4인데 2레벨은..

https://www.acmicpc.net/problem/1343 아이디어 XXXXXX 를 AAAABB로 만드는 방법중에서, 정답은 사전순으로 먼저 오는 것을 출력해야 하기 때문에 BBAAAA가 아니라 AAAABB가 정답이다. 따라서 A를 먼저 치환해야한다는 생각을 했다. XXXX를 AAAA로, XX를 BB로 치환을 하는 것이다. 이것으로 치환이 안되면 만들 수 없는 경우이다! 따라서, XXXX와 XX를 각각 A와 B로 치환을 한 후, X가 여전히 포함되어 있다면 만들 수 없는 경우이므로 -1을 출력한다. 코드 풀이 s = input() a = s.replace("XXXX","AAAA") # 사전 순으로 가장 앞서는 답을 출력해야하므로 A 부터 치환한다 b = a.replace("XX", "BB") pr..

https://www.acmicpc.net/problem/2644 입력 9 7 3 7 1 2 1 3 2 7 2 8 2 9 4 5 4 6​ 출력 3​ 코드 풀이 import sys n = int(sys.stdin.readline().rstrip()) p1, p2 = map(int, sys.stdin.readline().rstrip().split()) m = int(sys.stdin.readline().rstrip()) family = [[] * (n+1) for _ in range(n+1)] visited = [False] * (n+1) result = 0 flag = False for _ in range(m): x, y = map(int, sys.stdin.readline().rstrip().split(..

https://www.acmicpc.net/problem/4963 입력 1 1 0 2 2 0 1 1 0 3 2 1 1 1 1 1 1 5 4 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 1 0 0 1 0 5 4 1 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 5 5 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0​ 출력 0 1 1 3 1 9​ 코드 풀이 전형적인 DFS 문제이다. 1012 유기농 배추와 비슷한 문제이고, 체크할 방향이 상하좌우 뿐만 아니라 대각선 체크가 추가되었다. import sys sys.setrecursionlimit(10**6) def dfs(x,y): if x =h or y < 0 or..