1781 컵라면, 9663 N-Queen, 1987 알파벳

1781 컵라면, 9663 N-Queen, 1987 알파벳

 

1781 컵라면

import heapq

n = int(input())
array = []
q = []

for _ in range(n): # take deadline, number of noodle and sorting
	x, y = map(int, input().split())
	array.append((x, y))
array.sort()

for i in array: # add noodles and if deadline over, delete minimum value in list
	a = i[0]
	heapq.heappush(q, i[1])
	if a < len(q):
		heapq.heappop(q)
print(sum(q))

- 두 원소 받아서 튜플로 정리할 수 있음

- 두 원소 받아서 array.sort() 하면 첫번째 원소를 기준으로 정렬

 

 

9663 N-Queen

def check(x):
	for i in range(x):
		if row[x] == row[i]:
			return False
		if abs(row[x] - row[i]) == x - i:
			return False
	return True
	
def dfs(x):
	global result
	if x == n:
		result += 1
	else:
		for i in range(n):
			row[x] = i
			if check(x):
				dfs(x+1)
				
n = int(input())
row = [0] * n
result = 0
dfs(0)
print(result)

- 같은 코드인데 계속 시간 초과 뜨다가 통과하기도 한다. 왜그러는지..

- 계속 봐도 이해가 안되는 코드..(dfs function part)

 

 

1987 알파벳

# 첫번째 풀이 (틀림)
def check(x):
	if x in check_array:
		return True
	return False

def dfs(v, w):
	global result, max_value
	if check(array[v][w]):
		if result > max_value:
			max_value = result
		return result
	check_array.append(array[v][w])
	result += 1
	directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]
	for nx, ny in directions:
		dx, dy = v + nx, w + ny
		if dx < 0 or dx >= r or dy < 0 or dy >= c:
			continue
		else:
			dfs(dx, dy)
				
r, c = map(int, input().split())
array = [[] * c for _ in range(r)]
check_array = []
result = 0
max_value = 0
for i in range(r):
	array[i] = list(input())
	
dfs(0, 0)
print(max_value)

# 두번째 풀이
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
	global result
	q = set()
	q.add((x, y, array[x][y]))
	
	while q:
		x, y, step = q.pop()
		result = max(result, len(step))
		
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			
			if (0 <= nx and nx < r and 0 <= ny and ny < c and array[nx][ny] not in step):
				q.add((nx, ny, step + array[nx][ny]))
				
r, c = map(int, input().split())
array = []
for _ in range(r):
	array.append(input())
	
result = 0
bfs(0, 0)
print(result)

- 발상은 괜찮았는데.. 아쉽

- list(input()) => 문자열 받아서 한 자씩 끊어서 리스트로 저장