나만의 개발블로그

처음 접근해본 풀이 방법으로 분할과 정복 문제는 처음 배울때 재귀로 배웠어서 아래와 같이 접근했는데 아직 알고리즘을 쉽게 푸는 방식에 대해 깨닫지 못했는지 코드도 길고 시간도 꽤나 걸렸다. def CTP(li): global k, n if len(li) == 1: return li mid = len(li)//2 left, right = CTP(li[:mid]), CTP(li[mid:]) if k == n//mid: result.append(left+right) return sorted(left+right) import sys input = sys.stdin.readline n = int(input()) li = list(map(int,input().split())) k = int(input()) resu..

문제 해결 방법으로는 시작 시간과 종료 시간을 기준으로 화물차 작업 시간을 담은 배열을 내림차순 정렬 그리고 가장 중요했던 포인트로 오름차순 정렬을 한 뒤 종료 시간과 현재 시작 시간을 비교하며 나아가보니 중간에 시간을 많이 차지하는 경우가 있더라도 그냥 체크를 하고 넘어가서 문제가 되기에 내림차순 정렬을 해서 조사를 하는 것이 포인트가 되는 것 같다. for tc in range(1, int(input())+1): n = int(input()) form = [list(map(int,input().split())) for _ in range(n)] form.sort(key=lambda x:(x[0], x[1]), reverse=True) result = 0 for x in range(n): s,e = f..

문제 해결 방법으로는 화물의 무게와 트럭 적재용량을 내림 차순 정렬 후 추가된 개수만큼 idx를 증가시키며 찾도록 했다. for tc in range(1,int(input())+1): n,m = map(int,input().split()) w_li = sorted(list(map(int,input().split())), reverse=True) # 화물 무게 t_li = sorted(list(map(int,input().split())), reverse=True) # 트럭 적재 용량 cnt, hap = 0, 0 # 적재된 횟수. 누적 합 for i in range(n): if t_li[cnt]>=w_li[i]: cnt, hap = cnt +1, hap+w_li[i] if cnt == m: break pr..

흠... 너무 오래걸렸다.. 오래 걸린 이유는 아래와 같은 tc의 경우에 [0,1]인 18부터 시작할 경우 우선 48,55 이렇게 두 가지 경로로 갈 수가 있는데 48로 가는 순간 다시 0번째 행으로 가게 되어서 34를 조회하게 되는 경우가 발생하게 되는 것 때문에 너무 오래 걸렸다... 0 18 34 48 0 55 18 7 0 그래서 1로 가지 않게 for문을 1, n으로 두고 마지막에 cnt 가 n-2의 경우에 s행의 0번째 인덱스 값을 더해줘 해결하도록 했음. def search(s, hap, cnt): global mx_hap if cnt == n-2: mx_hap = min(mx_hap, hap+arr[s][0]) return if hap >= mx_hap: return for i in rang..

주의점으로는 elif 문을 추가해 hab이 현재 result 값 보다 큰 값일 경우엔 더 이상 조사하지 않도록 해주기! for tc in range(1, int(input())+1): n = int(input()) arr = [list(map(int,input().split())) for _ in range(n)] result = 11*n*n # dfs 사용 stack = [[0, 0, arr[0][0]]] while stack: x,y,hab = stack.pop() if x == n-1 and y == n-1: if result > hab: result = hab continue elif hab >= result: continue # 오른쪽, 아래만 탐색 for i,j in [[0, 1], [1, 0..

답이 잘 나왔는데 에러가 나길래 확인해보니... 파일의 끝에서 입력을 멈춘다를 잊고 있었다... 그래서 EOF(End of File) 예외처리를 통해 해결 그리고 처음에는 배열을 이용해서 풀어보려고 파라미터로 n과 해당 함수가 가질 수 있는 가장 큰 인덱스 값도 함께 넣어줬는데 그냥 이렇게 푸는게 더 편해서 ㅎㅎ def cantoer(n): if n == 1: return '- -' else: return cantoer(n-1) + ' '*(3**(n-1)) + cantoer(n-1) while True: try: n = int(input()) if n == 0: print('-') else: print(cantoer(n)) except EOFError:break

가장 단순히 1보다 작거나 같을 경우에 return 하는 재귀 풀이 def fectorial(n): if 1>=n: return 1 return n*fectorial(n-1) print(fectorial(int(input()))) 배열에 값을 추가하면서 해당 값이 존재하다면 바로 return 하는 재귀 풀이 def fectorial(n): if li[n]: return li[n] li[n] = n*fectorial(n-1) return li[n] n = int(input()) li = [0]*(n+1) li[0] = 1 fectorial(n) print(li[n])

SWEA를 푸는게 오랜만이라 무심코 tc를 그냥 i로 지정해놓고 출력했는데 답은 맞는데 왜 풀리지 않을까라고 생각하고 보니 아래의 3번째 for문에 i를 사용하고 있었어서 시간을 조금 보냈다... (주의하기!!) for tc in range(int(input())): n,m = map(int,input().split()) li = [float('inf')] for _ in range(m): li2 = list(map(int,input().split())) for i in range(len(li)): if li[i] > li2[0]: li[i:i] = li2 break li.reverse() print('#%d'%(tc+1), end=' ') print(*li[1:11])

for i in range(int(input())): # TC cnt n,m,l = map(int,input().split()) li = list(map(int,input().split())) for _ in range(m): idx,num = map(int,input().split()) li = li[:idx]+[num]+li[idx:] print('#%d %d'%(i+1,li[l]))

아래 코드는 2차원 배열을 활용해 푸는 방법 아직도 dp를 활용하여 누적합을 만들어 내는 로직을 구현하는데에 많은 어려움이 있어서 여러 방법을 찾아보려고 노력중. 우선 아래 코드에서 else 구문에 dp[i][j-1] 을 추가하여 max로 값을 찾는 이유에 대한 의문을 제기할 수 있다. 결과적으로는 저 코드를 추가함으로서 이전에 나온 값이 이만큼 나온적이 있다라는 의미가 되는데 ACAYKP CAPCAK 예시를 들어보자면 i가 2의 경우 a = 'C' j = 1일 땐 b = 'C' 가 될 때는 같기에 이전까지의 누적 합에 해당하는 dp[i-1][j-1] 에서 +1 해주고 j = 2일 땐 b = 'A' 가 될 때는 다르니 현재의 dp 값에는 i-1 층에 해당하는 현재 j 값과, j 가 1이었을 때의 값 중 ..