clohi 님의 블로그

https://www.acmicpc.net/problem/11048 문제 코드import sysinput = sys.stdin.readlinen, m = map(int, input().split())dp = [[0 for _ in range(m+1)] for _ in range(n+1)]maze = []for i in range(n): maze.append(list(map(int, input().split())))for j in range(1, n+1): for k in range(1, m+1): dp[j][k] = max(dp[j-1][k-1], dp[j-1][k], dp[j][k-1]) + maze[j-1][k-1]print(dp[n][m]) 문제 풀이 - dp dp로 어렵지..

https://www.acmicpc.net/problem/1744 문제 코드 import sysinput = sys.stdin.readlinen = int(input())arr_minus = []arr_plus = []is_zero = Falseans = 0for i in range(n): x = int(input()) if(x > 1): arr_plus.append(x) elif(x 문제 풀이 - 그리디 처음 문제를 봤을 때는 어떤 식으로 접근해야 할 지 감이 안 잡혔는데 계속 뚫어져라(?) 쳐다보니깐 어느 순간 풀이가 떠올랐다. 일단 입력받는 수를 양수와 음수로 구분해서 양수는 큰 순서대로 두 개의 양수끼리 곱하는게 무조건 이득이고 음수는 작은 순서대로 곱하는게 무조건..

https://www.acmicpc.net/problem/2003 문제 코드 import sysinput = sys.stdin.readlinen, m = map(int, input().split())arr = list(map(int, input().split()))left = 0right = 0cnt = 0current_sum = arr[0]while True: if current_sum 문제 풀이 - 투 포인터 투 포인터를 사용하여 문제를 풀었다. left, right로 두 개의 포인터를 만들고 1) 부분합이 M보다 작으면 → 오른쪽 포인터 증가2) 부분합이 M보다 크면 → 왼쪽 포인터 증가3) 부분합이 M과 같으면 → 카운트 +1, 왼쪽 포인터 증가 위의 방식으로 부분합을 비교해서 경우의 수..

https://www.acmicpc.net/problem/1038 문제 코드 from itertools import combinationsimport sysinput = sys.stdin.readlinen = int(input())arr = []for i in range(1, 11): for j in combinations(range(10), i): num = sorted(j, reverse=True) arr.append(int("".join(map(str, num))))arr.sort()if(len(arr) 문제 풀이 - 완전탐색, 조합조합을 이용해서 감소하는 수를 모두 찾아 배열에 넣고 n번째 감소하는 수를 찾는 식으로 풀었다. for i in range(1, 11..

https://www.acmicpc.net/problem/3986 문제 코드 import sysinput = sys.stdin.readlinen = int(input())cnt = 0for i in range(n): word = input().rstrip() stack = [] for j in range(len(word)): if(stack and stack[-1] == word[j]): stack.pop() else: stack.append(word[j]) if(not stack): cnt += 1print(cnt) 문제 풀이 - 자료구조(스택) 문제만 이해하면 쉽게 풀 수 있는 문제다. 단어의 왼쪽 글..

https://www.acmicpc.net/problem/1026 문제 코드import sysinput = sys.stdin.readlinen = int(input())arr1 = list(map(int, input().split()))arr2 = list(map(int, input().split()))arr1.sort()arr2.sort(reverse=True)ans = 0for i in range(n): ans += arr1[i] * arr2[i]print(ans) 문제 풀이 -그리디 알고리즘 두 배열 A, B가 있고 S = A[0] × B[0] + ... + A[N-1] × B[N-1] 에서 S를 최소로 만드려면 A의 가장 작은 값을 B의 가장 큰 값과 곱하고, 그 다음 A의 작은 값을 B의..

https://www.acmicpc.net/problem/5972 문제 코드import heapqimport sysinput = sys.stdin.readlineINF = int(1e9)n, m = map(int, input().split())graph = [[] for _ in range(n+1)]distance = [INF for _ in range(n+1)]for i in range(m): a, b, c = map(int, input().split()) graph[a].append((b,c)) graph[b].append((a,c))def dijkstra(start): q = [] heapq.heappush(q, (0, start)) distance[start] = ..

https://www.acmicpc.net/problem/14248 문제코드 import sysinput = sys.stdin.readlinen = int(input())arr = list(map(int, input().split()))arr.insert(0, 0)s = int(input())visited = [False] * (n+1)def dfs(arr, s, visited): if(not visited[s]): visited[s] = True if(s + arr[s] 0): dfs(arr, s-arr[s], visited)dfs(arr, s, visited)print(sum(visited)) 풀이 - DFS 사용 DFS를 사용하면 쉽게 풀리는 문제이다. 물론 B..