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)..
https://www.acmicpc.net/problem/11725 1 - 6 => 1을 통해서 둘 중 부모가 1이란 것을 알 수 있음1. 입력받은 연결을 가지고 인접 행렬 만듦 2. 1부터 차례대로 트리 연결하며, 배열에 부모 저장 3. 저장한 배열 출력1 - 6 - 3 - 5 - 4 - 2 - 7 이렇게 자식이 하나 이상인 경우가 있기 때문에, 인접 행렬에서 부모를 뺀 후 iter의 형태로 자식들을 모두 스택에 넣어야 한다.import sysfrom collections import defaultdictinput=sys.stdin.readlineadj = defaultdict(list)n = int(input())parent = [0 for _ in range(n+1)]for _ in..
https://www.acmicpc.net/problem/1987BFS 로 처리 어려움➡️왜냐하면 지금까지 지나왔던 알파벳을 누적 저장해야 함따라서 Backtracking으로 처리하되, 길을 더 갈 수 없다면 지금까지 경로 길이를 이전에 저장해둔 최장의 길이와 비교하여 더 길 경우 갱신알파벳의 경우 갯수가 정해져 있으므로 boolean 타입의 길이 26인 배열 사용하여 지금까지 지나 온 알파벳 체크 그러나 dfs로 모든 루트 검사할 경우, 반복적으로 같은 지점 들릴 수 있음 => DP 사용하여 반복 계산 줄이기import sysfrom collections import dequeinput = sys.stdin.readliner, c = map(int, input().split())board = [inpu..
https://www.acmicpc.net/problem/15666import sysinput= sys.stdin.readlinen,m = map(int, input().split())num = sorted(set(map(int, input().split())))arr=[]def dfs(start, depth): if depth==m: print(*arr) return for i in range(start, len(num)): arr.append(num[i]) dfs(i, depth+1) arr.pop()dfs(0,0)
https://www.acmicpc.net/problem/2161deque를 사용해 맨 앞과 뒤에서 pop, push 일어나는 것 사용!from collections import dequeimport sysn = int(sys.stdin.readline())cards = deque(i for i in range(1, n+1))while cards: print(cards.popleft(), end=" ") if cards : cards.append(cards.popleft())
https://www.acmicpc.net/problem/15649백트래킹 기법을 통해 출력import sysinput = sys.stdin.readlinen, m = map(int, input().split())check = [False] * (n+1)num = []def dfs(left): # 남은 개수가 0이면 지금까지 쌓은 조합/순열을 출력 if left == 0: print(*num) return for i in range(1, n+1): if not check[i]: check[i] = True # i를 선택했으니 표시 num.append(i) # 경로에 추가 ..
https://www.acmicpc.net/problem/3085문제에 제대로 나와 있지 않아 처음에 조금 고민했는데,알고 보니 딱 하나를 옆의 것과 바꿨을 때를 고려하는 것이다.즉, 현재 사탕과 다른 바로 옆/아래의 사탕을 바꿨을 때의 연속된 같은 사탕 개수 중 최대 값을 구하면 된다.그냥 브루트포스 문제이다.import sysinput = sys.stdin.readlinemaxcnt=0n = int(input())board=[]for _ in range(n): board.append(list(input().rstrip()))def checkarr(board, x): global maxcnt secnt=1 for j in range(1,n): if board[j-1][..
https://www.acmicpc.net/problem/14501import sysinput= sys.stdin.readlinen = int(input())dp=[[0,0] for _ in range(n+1)]for i in range(1,n+1): dp[i] = list(map(int,input().split())) # t, p maxsum= max((x[1] for x in dp[:i] if x[0] 해당 문제는 DP 문제로,현재 시점에서 상담을 채택한다고 했을 때, 현재 상담이 가능케 하는 상담 기록 중 누적 합이 가장 큰 값을 골라서, 현재 상담의 값을 더해 저장하고, 이 상담을 채택했을 때 다음 상담은 언제 가능한지 기록한다.즉,다음 상담 가능 날짜 / 누적값이런 형태로 저장하면 된..
https://www.acmicpc.net/problem/25206자릿수 제한 없이 오차 10^-4 이하면 정답으로 인정되기 때문에, 딱히 자릿수를 건드리거나 할 필요 없이 계산하면 된다.import sysinput= sys.stdin.readlinesum=0cnt=0degdict = { 'A+': 4.5, 'A0': 4.0, 'B+': 3.5, 'B0': 3.0, 'C+': 2.5, 'C0': 2.0, 'D+': 1.5, 'D0': 1.0, 'F': 0.0}for _ in range(20): arr = list(input().split()) if arr[2]=='P': continue sum+=degdict[arr[2]]*float(a..
