[구름톤 챌린지] 3주차_ 14~ 15일차 학습

Day14 작은 노드 - 구름LEVEL (goorm.io)

내 풀이 과정

노드가 무엇인가...아무런 배경지식이 없었다 노드, 양방향 노드 등 여러가지 검색을 통해 노드를 생성하고 이동하는 방법으로 문제를 해결하고 나서 보니 그래프 라는 단어가 보였다. 그래프에 대해서 다시 공부하기로 했고 다음날 해설코드와 비교해 보았다. 아래는 노드를 만들고 아주 비효율적으로 해결한 코드다.

 

# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
N, M, K = map(int, input().split())

class node(object):
	def __init__(self, data=None, prev = None, next = None):
		self.data = data
		self.prev = []
		self.next = []

	def printNode(self):
		print(self.data, self.prev, self.next)
	
def scanNode(start):
	nodes[start].data = 1
	current = start
	steps = 0
	
	while not current in trace :
		latest = current
		trace.append(current)
		steps += 1
		scan = nodes[current].prev + nodes[current].next
		scan.sort(reverse = True)
		while scan:
			check = scan.pop()
			if nodes[check].data == 0 :
				current = check
				nodes[check].data = 1
				break
		
	print(steps, latest)
		

nodes = []
nodes.append(node('head'))
trace = []
for _ in range(1, N+1):
	nodes.append(node(0))

for _ in range(M):
	l, r = map(int, input().split())
	nodes[l].next.append(r)
	nodes[r].prev.append(l)

scanNode(K)

 

정해 코드

훨씬 더 깔끔한 코드로 작성되어 있었다. 상상한바를 간단하게 풀어내는 능력이 참 부럽다.. 나와는 맞지 않는 분야인것 같다. 포기해야하나..

 

import sys
sys.setrecursionlimit(10**4)

def dfs(now):
	for to in sorted(graph[now]):
		if not visited[to]:
			visited[to] = 1
			return dfs(to)
	else:
		return now

N, M, K = map(int, input().split())
graph = [[] for _ in range(N + 1)]
visited = [0] * (N + 1)

for _ in range(M):
	s, e = map(int, input().split())
	graph[s].append(e)
	graph[e].append(s)

visited[K] = 1
result = dfs(K)
print(sum(visited), result)

Day15 과일 구매 - 구름LEVEL (goorm.io)

내 풀이 과정

그리디 문제라고 해서 나눗셈이나 하면 되겠지 생각하고 덤볐으나 조금더 생각을 하게 만드는 문제였다.

나는 주어진 과일정보를 통해 1코스트의 포만감을 먼저 구했고, 총 구매가능한 조각을 참고하여 현재 가진 돈으로 가장 큰 포만감의 과일조각부터 해치우는순으 최대 포만감을 구해주었다. 

 

# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
N, K = map(int, input().split())
fruits = [list(map(int, input().split())) for _ in range(N)]
fruits = [[int(fruits[x][0]) ,int(fruits[x][1]/fruits[x][0])] for x in range(N)]
fruits.sort(key = lambda x:(x[1], x[0]))

fomangam = 0
while K > 0:
	if fruits :
		f = fruits.pop()
		if K > f[0] : fomangam += f[0]*f[1]
		else : fomangam += K*f[1]
		K -=f[0]
	else: break
print(fomangam)

사실 그전에 모두 조각내서 리스트에 추가하는 방법을 사용해볼까 했으나 테스트케이스에 10억이 있는것을 보고 포기 했다.

모두 조각내서 넣는 방법을 사용하면 아래와 같은 오류가 발생한다.

input
1 1
1000000000 1000000000

output
make: *** [cmd] Error 137

answer
1

 

정해 코드

해설에서는 필요할 경우에만 과일을 쪼개서 먹는방법을 사용했다. 음... 이렇게하면 계산 횟수를 좀 더 줄일 수 있을듯 하다.

 

N, K = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

arr.sort(key=lambda x : x[1] // x[0])

result = 0

while K and arr:
	P, C = arr.pop()
	
	if K >= P:
		result += C
		K -= P
	else:
		result += C // P * K
		K = 0

print(result)