Algorithm475 [파이썬] 백준 11281 : 2-SAT - 4 (플레3) [파이썬] 백준 11281 : 2-SAT - 4 (플레3)https://www.acmicpc.net/problem/11281풀이방향성 생각2 SAT 기본 문제 + 명제 추정하기입력이 들어오면 음수 노드를 양수로 만들어서 매핑해준다.풀고 알았는데, 보통 짝수를 참, 홀수를 거짓으로 매핑해서 각 node 0을 새로운 new node 0,1로 매핑한다.명제가 들어오면 전처리 이후, 대우 명제와 함께 그래프에 넣어주기.한 SCC 내에 x와 ~x가 같이 존재하면 모순이므로 명제를 참으로 만들 수 없다.모순이 발생하지 않으면 진입 차수가 낮은 노드부터 false를 매겨주고, 그 node의 부정은 true를 매겨준다. 전체코드import syssys.setrecursionlimit(10**6)input = lambd.. 2025. 4. 16. [파이썬] 백준 11280 : 2-SAT - 3 (플레4) [파이썬] 백준 11280 : 2-SAT - 3 (플레4)https://www.acmicpc.net/problem/11280풀이방향성 생각2 SAT 기본 문제입력이 들어오면 음수 노드를 양수로 만들어서 매핑해준다.풀고 알았는데, 보통 짝수를 참, 홀수를 거짓으로 매핑해서 각 node 0을 새로운 new node 0,1로 매핑한다.명제가 들어오면 전처리 이후, 대우 명제와 함께 그래프에 넣어주기.한 SCC 내에 x와 ~x가 같이 존재하면 모순이므로 명제를 참으로 만들 수 없다. 전체코드import syssys.setrecursionlimit(10**6)input = lambda : sys.stdin.readline().strip()# 입력N,M = map(int,input().split())cvt = la.. 2025. 4. 16. [파이썬] 백준 1038 : 감소하는 수 (골드5) [파이썬] 백준 1038 : 감소하는 수 (골드5)https://www.acmicpc.net/problem/1038풀이방향성 생각재귀 기본문자열을 계속 붙여서 끝에 0이 나오는 경우, 감소수열을 더 만들지 못하므로 리턴으로 탈출하기. 전체코드N = int(input())if N nx: dfs(x+nx) dfs('') # 정렬 기준은 문자열이 아닌 숫자로 arr.sort(key = lambda x : int(x)) try: print(arr[N]) except: print(-1)코멘트문자열로 풀었으면 정렬 기준만 다시 생각해주기. 2025. 4. 15. [파이썬] 백준 2293 : 동전1 (골드4) [파이썬] 백준 2293 : 동전1 (골드4)https://www.acmicpc.net/problem/2293풀이방향성 생각unbounded knapsack현재 선택한 동전으로 가방을 모두 채운다.다음 선택한 동전으로 가방을 모두 채운다. 반복현재 value에서 gain을 뺐을 때 음수가 오는 곳에서 인덱스 에러만 처리해주며 된다. 전체코드import syssys.setrecursionlimit(10**6)N,K = map(int,input().split())arr = [int(input()) for _ in range(N)]dp = [[-1]*(K+1) for _ in range(N)]def dfs(idx,x): # 기저조건 if not x: return 1 # 마지막 동전.. 2025. 4. 15. 이전 1 2 3 4 5 6 7 8 ··· 119 다음
