https://www.acmicpc.net/problem/11052n개의 카드를 사는 경우에 금액이 최대인 것을 찾아야 한다.c[1]+c[2] >c[3] 더한 값이 원래 값보다 크면 바꾼다.카드팩 동일한 것을 여러 번 살 수 있으므로 현재의 인덱스가 1이면 더해주는 인덱스 범위는 1~ n-1 import sysinput = sys.stdin.readlinen = int(input())cards = [0]+list(map(int, input().split())) # 1 ~ nfor i in range(1,n+1): #1 ~ n까지 인덱스 for next in range(i,n-i+1): if cards[i]+cards[next] > cards[i+next]: card..
https://www.acmicpc.net/problem/6064다른 분들 푼 거 보면 어쩌구 정리 같은거 사용해서 푸시던데, 나는 그런 것 없이 구현으로 풀었다!우선 범위가 이기 때문에, M, N의 최대공배수까지 반복문을 돌리게 하였고,x-1을 시작으로 m씩 증가시키면서 이게 y도 충족시키는 지 확인하였다.m과 n 둘 중 큰 숫자를 기준으로 증가시키면 더 좋겠지만, 그렇게까지 안 해도 시간초과는 되지 않았다!시간 복잡도는 O(N)이다.import sys, mathinput=sys.stdin.readlinet = int(input())def cal(M, N, x, y): for i in range(x-1, abs(M*N)//math.gcd(M,N), M): ny = i%N+1 ..
https://www.acmicpc.net/problem/11286힙의 정렬이 작은 수부터 큰 수로, 그리고 객체가 튜플일 경우 좌->우로 정렬 기준을 잡는다는 것을 사용하면 된다.절댓값이 작은 것부터, 같은 게 있다면 실제 값이 작은 것부터 이므로 힙에 넣는 숫자를 [절댓값, 값]의 순으로 튜플 형태로 넣으면 된다.import sys, heapq,mathinput=sys.stdin.readlinen = int(input())heap = []ans=""for _ in range(n): x= int(input()) if x==0 : if heap: ans+=str(heapq.heappop(heap)[1])+"\n" else : ans+="0\n" else : h..
https://www.acmicpc.net/problem/1991이진 트리의 순회를 어떻게 구현해야 할 지 고민했을 때, 내가 생각한 방법은 세 가지였다.Node 클래스 구현하여 부모 자식 관계 명시하는 데이터타입 사용배열을 사용하되, 인덱스로 트리 부모 자식 관계 찾을 수 있게이 문제에서는 처음에 노드 총 개수를 처음에 제시해주는데, 이 방법은 트리의 깊이에 따라서 배열의 크기를 설정해줘야 하기 때문에 부적절해보인다.dict 사용해서 부모가 키, 자식이 value로 들어가게해당 문제에서는 좌, 우 중 하나가 없을 때 .으로 표시되어 순회 시 좌, 우를 알 수 있다. 이 문제에서는 자식이 하나만 있을 시 좌우가 중요하진 않긴 하다이중 가장 간단해 보이는 dict를 사용하도록 하겠다. import sysi..
https://www.acmicpc.net/problem/30804아래는 시간초과 되는 답안!!O(n^2)라 별로 좋지 않다...import sysinput = sys.stdin.readlinen = int(input())answer = min(n, 2)fruits = list(map(int, input().split()))for i in range(n-2): print(i) if n-i 2 : break x+=1 answer = max(x-i, answer)print(answer)밑은 맞은 답안!숫자가 같고 묶여있는 것끼리 압축해준다[숫자, 개수] 의 형태로 묶여있는 것을 가지고 투 포인터를 진행한다!from collections import defaultdictimport..
https://www.acmicpc.net/problem/11049그리디로 현재 상황에서 가장 중간에 곱해지는 값이 큰 행렬을 없애면 되는 줄 알았으나,그것이 최적해를 보장하지 않는다는 것을 알게되었다!!어쩔 수 없이 DP로 풀어야 한다.import sysinput=sys.stdin.readlinen = int(input())dims = []for i in range(n): r ,c = map(int, input().split()) if not dims : dims.extend([r,c]) else: dims.append(c) # c만 저장dp = [[0 for _ in range(n)] for _ in range(n)]for l in range(2, n+1): for i in ra..
https://www.acmicpc.net/problem/12865당연히 Knapsack problem이다.dp를 사용해서, 물건의 중량을 배열의 인덱스로, 안의 값을 해당 중량이었을 때의 최대 가치를 저장하는 데 사용한다.물건의 중량과 가치가 입력될 때마다, 최대 중량부터 해당 물건의 중량 초과일 때까지의 인덱스를 뒤부터 앞으로 돌며해당 중량을 넣었을 때와 넣지 않았을 때(기존에 저장되어 있던 값)을 비교하여, 둘 중 큰 값을 저장한다.뒤에서부터 앞으로 도는 이유는, 앞부터 저장하게 되면 해당 물건을 여러 번 저장하게 될 수 있어서이다..이렇게 물건을 넣었을 때의 케이스들을 따져본 후, 해당 물건만 들어갔을 때도 저장해준다. 이때도 기존 저장 가치와 비교해서 저장한다.import sysinput=sys..
https://www.acmicpc.net/problem/171441. 미세먼지 확산 - 1-1. 지금 미세먼지 있는 곳 확인 - 스택에 넣어 - 1-2. 스택에 있는 거 다 처리(확산, 계산)하면서 새로 생성은 스택에 넣지 x ** 스택 써야 하는 이유 : 현재 자리의 미세먼지 확산 시 옆에 값들이 확산된건지아닌건지알수가없음... 그래서 스택써야햄.. 2. 공청기 작동 3. 다시 스택에 미세먼지 스팟들 넣음.. t초가 될 때까지 반복 t초 후 양수인 곳들 필터링해서 sumimport sysr,c,t = map(int, input().split())a = [] # r x cairp=[] for y in range(r): # air_purifier -> -1, else -> >0 a.append..
https://www.acmicpc.net/problem/1043testcase.ac에서도 모든 테스트케이스를 통과하고, 질문게시판에 있는 모든 예제들도 다 통과해서 도대체 뭐가 문제인지..왜 3%에서 계속 틀리는 지 고민했던 문제이다.알고 보니, pop_party 함수에서 ppl 리스트 값을 통해 party를 제거할 때, 여기서 거짓말 불가한 사람을 더해주지 않아서 그런 거였다! 거짓말 불가한 사람을 통해 다시 그 사람이 참석한 파티가 거짓말 불가함을 판정할 때, 이렇게 퍼져 나갈 때 거짓말 불가한 사람 리스트(knows)에 제대로 사람을 추가했는 지 확인해보길..import sysfrom collections import defaultdictinput=sys.stdin.readlinen, m = m..
https://www.acmicpc.net/problem/13549import sysfrom collections import dequeinput = sys.stdin.readlinen, k = map(int, input().split())p = [-1 for _ in range(100001)]dq = deque([n])p[n]= 0while dq: x= dq.popleft() if x==k : print(p[k]) break if 0p[x]): p[2*x]=p[x] dq.appendleft(2*x) # 우선 처리 if 0p[x]): p[x-1] = p[x]+1 dq.append(x-1)..
