본문 바로가기

분류 전체보기

 (402)
[백준 13560번] 축구 게임 (Python3) def solve(): if sum(win) != N*(N-1)//2: return -1 upset = 0 for i in range(N): upset += win[i]-i if upset < 0: return -1 return 1 N = int(input()) win = sorted(map(int,input().split())) print(solve()) 그리디 알고리즘 문제 아이디어를 떠올리지 못하여, 질문게시판에서 힌트를 얻어 해결하였다. (참고 https://www.acmicpc.net/board/view/72090) 풀이를 설명하면, 1. 승리수가 N(N-1)/2가 아니라면 당연히 -1이다. 2. 승리수를 오름차순으로 정렬한다. 3. i번째 팀에 대해서, 현재 팀보다 못하는 팀을 모두 이긴다고 ..
[백준 11658번] 구간 합 구하기 3 (Python3) import sys input = sys.stdin.readline def update(y,x,v): while y
[백준 14578번] 영훈이의 색칠공부 (Python3) N = int(input()) DP = [0]*(N+2); DP[2] = 2 for n in range(3,N+1): DP[n] = DP[n-1]*n*(n-1) + DP[n-2]*n*(n-1)**2 DP[n] %= 10**9+7 print(DP[N]) DP로 해결하였다. 까다로운 문제였다. 아이디어를 떠올리기 쉽지 않았다. 아이디어를 설명하면, 1. i번째 줄과 j번째 줄이 같은 칸에서 하나는 파란색, 하나는 빨간색일 때, i번째 줄과 j번째 줄을 "연결되어있다" 라고 정의하자. 2. i번째 줄과 j번째 줄은 두번 연결되어있을 수도 있고, 한번만 연결되어 있을 수 있다. 3. N번째 줄을 추가할 때, N-1번째 줄과 연결되어있다고 가정하자. 그러면 N-1줄과 N줄은 두번 연결된 경우가 있을 수 있고, 한..
[백준 23089번] 사탕나무 (Python3) import sys input = sys.stdin.readline sys.setrecursionlimit(10**5) def BFS(): dq = [1] while dq: now = dq.pop() for next in graph[now]: if not child[next]: parent[next] = now child[now].append(next) dq.append(next) def DFS(now): childDP[now][0] = 1 for next in child[now]: DFS(next) for k in range(K): childDP[now][k+1] += childDP[next][k] def count(now): DP[now][0] = 1 for k in range(K): DP[now][..
[백준 15554번] 전시회 (Python3) import sys input = sys.stdin.readline N = int(input()) art = sorted([*map(int,input().split())] for i in range(N)) S = sum(art[i][1] for i in range(N))+art[0][0]-art[-1][0] prefix1 = [0]; prefix2 = [0] for i in range(N-1): prefix1.append(prefix1[-1]+art[i+1][0]-art[i][0]-art[i][1]) prefix2.append(prefix2[-1]+art[-i-1][0]-art[-i-2][0]-art[-i-1][1]) arr1 = [(0,-1)]; arr2 = [(0,N)] for i in range(1..
[백준 10165번] 버스 노선 (Python3) import sys input = sys.stdin.readline from collections import * input(); N = int(input()) bus = [] for i in range(1,N+1): a,b = map(int,input().split()) bus.append((a,-b,i)) bus.sort() stack1 = deque(); stack2 = deque() for a,b,i in bus: b = -b if a
[백준 1053번] 팰린드롬 공장 (Python3) from itertools import * def DFS(start,end,DP): for i,j in [(1,0),(0,1),(1,1)]: if DP[start+i][end-j]==N: DFS(start+i,end-j,DP) DP[start][end] = min(DP[start][end],DP[start+i][end-j]+int(not(i and j and seq[start]==seq[end]))) def palin(): if N==1: return 0 DP = [[N*int(i
[백준 13308번] 주유소 (Python3) import sys input = sys.stdin.readline from heapq import * def dij(): hq = [(0,cost[0],0)]; DP = [[1e12]*N for i in range(cost[0]+1)] while hq: w,c,now = heappop(hq) if now==N-1: return w if DP[c][now] w+w1*c: DP[c1][next] = w+w1*c heappush(hq,(w+w1*c,c1,next)) N,M = map(int,input().split()) cost = [*map(int,input()..

티스토리툴바