- 또 티어 보고 쫄았다
- 삼성 기출이랜다 또 한번 쫄았다
- 테스트 케이스 다 맞추는데만 한세월 걸렸다
- 예상은 했지만 테케 다 맞추고 나니 시간초과
- 어떻게든 줄여볼려고 별 짓을 다 했지만 50퍼를 못넘기더라
- 답지 참고
- 유레카
wow
원래 짰던 코드
energy = []
tree = []
plusEnergy = []
N, M, K = map(int, input().split())
energy = [ [ 5 for i in range(N)] for j in range(N) ]
# 처음에 5로 양분 초기화
tree = [ [ [] for i in range(N)] for j in range(N) ]
# 처음에 나무 초기화
plusEnergy = [ [ 0 for i in range(N)] for j in range(N) ]
for i in range(N):
plusEnergy[i] = list(map(int, input().split()))
# 겨울에 추가될 양분 map
# print(plusEnergy)
for i in range(M):
row, col, value = map(int, input().split())
tree[row-1][col-1].append(value)
# 입력이 2 1 3 이면 tree[1][0] = 3
# print(max(tree[1][0]))
def printTreeFunc():
print("Tree")
for i in range(N):
for j in range(N):
print(tree[i][j], end = ' ')
print()
def printEnergyFunc():
print("Energy")
for i in range(N):
for j in range(N):
print(energy[i][j], end = ' ')
print()
dieTreeList = []
for i in range(K):
# K년 동안
print("봄 시작")
# 봄
for row in range(N):
for col in range(N):
if not tree[row][col]:
# 나무가 없으면 바로 재껴
continue
# print("before sort", tree[row][col])
tree[row][col].sort()
# 예를 들어서 나무가 2, 1, 5 있다 쳐
# print("after sort", tree[row][col])
if energy[row][col] >= sum(tree[row][col]):
# 안에 나무들 모두한테 양분을 줄 수 있으면?
for i in range(len(tree[row][col])):
energy[row][col] -= tree[row][col][i]
# 양분 마이너스
tree[row][col][i] += 1
# 전부 나이 1 증가
else:
# 양분이 부족하면?
print("양분이 부족하다. ")
printTreeFunc()
i = 0
while(tree[row][col]):
print("tree[row][col] = ", tree[row][col])
if i == len(tree[row][col]):
break
if tree[row][col][i] <= energy[row][col]:
# 있는 양분보다 나무 나이가 작으면
energy[row][col] -= tree[row][col][i]
# 양분 마이너스
tree[row][col][i] += 1
# 그 나무 나이 1 증가
i += 1
else:
dieTreeList.append([row, col, tree[row][col][i]])
tree[row][col].remove(tree[row][col][i])
print("row = ", row, " col = ", col, " i = ", i)
print("죽는 나무 ", dieTreeList)
# for i in range(len(tree[row][col])):
# # 나이가 어린 애부터
# print( "i = ", i)
# # print("tree[row][col] = ", tree[row][col])
# # print("tree[row][col][i] = ", tree[row][col][i])
# if tree[row][col][i] <= energy[row][col]:
# # 있는 양분보다 나무 나이가 작으면
# energy[row][col] -= tree[row][col][i]
# # 양분 마이너스
# tree[row][col][i] += 1
# # 그 나무 나이 1 증가
# else:
# dieTreeList.append([row, col, tree[row][col][i]])
# tree[row][col].remove(tree[row][col][i])
# print("row = ", row, " col = ", col, " i = ", i)
# print("죽는 나무 ", dieTreeList)
# break
# if energy[row][col] < max(tree[row][col]):
# # 죽는 나무 체크(나이가 제일 많은 나무의 나이보다 에너지가 없으면?)
# # 근데 나이가 어린 나무도 있잖아
# dieTreeList.append([row, col, max(tree[row][col])])
# # row, col, 나이
# tree[row][col].remove(max(tree[row][col]))
# 양분이 부족하면 나무 죽어
# else:
# # 양분 있으면 나이만큼 줄이고 나이 + 1
# maxIndex = tree[row][col].index(max(tree[row][col]))
# # 여러 나무들이 모여있을 때 최대값이 있는 인덱스는?
# energy[row][col] -= tree[row][col][maxIndex]
# # 나이 증가해주기 전에 있는 양분에서 나이만큼 줄여야지
# tree[row][col][maxIndex] += 1
print()
print("봄이 지나갔다")
printTreeFunc()
printEnergyFunc()
print("여름 시작")
# 여름
for row in range(N):
for col in range(N):
for i in range(len(dieTreeList)):
# print("row = ", row, " col = ", col, " i = ", i)
if dieTreeList[i][0] == row and dieTreeList[i][1] == col:
print("추가된 양분 = ", int(dieTreeList[i][2]/2))
energy[row][col] += int(dieTreeList[i][2]/2)
dieTreeList.clear()
# print()
print("여름이 지나갔다")
printTreeFunc()
printEnergyFunc()
print("가을 시작")
# 가을
for row in range(N):
for col in range(N):
if tree[row][col]:
for i in range(len(tree[row][col])):
if tree[row][col][i] % 5 == 0:
if row-1 >= 0 and col-1 >= 0:
tree[row-1][col-1].append(1)
if row-1 >= 0:
tree[row-1][col].append(1)
if row-1 >= 0 and col+1 < N:
tree[row-1][col+1].append(1)
if col-1 >= 0:
tree[row][col-1].append(1)
if col+1 < N:
tree[row][col+1].append(1)
if row+1 < N and col-1 >= 0:
tree[row+1][col-1].append(1)
if row+1 < N:
tree[row+1][col].append(1)
if row+1 < N and col+1 < N:
tree[row+1][col+1].append(1)
print()
print("가을이 지나갔다")
printTreeFunc()
printEnergyFunc()
print("겨울 시작")
# 겨울
for row in range(N):
for col in range(N):
energy[row][col] += plusEnergy[row][col]
print()
print("겨울이 지나갔다")
printTreeFunc()
printEnergyFunc()
answer = 0
for row in range(N):
for col in range(N):
answer += len(tree[row][col])
print(answer)깔끔한 코드
(프린트 찍으면서 확인하는 코드 다 지우고)
energy = []
tree = []
plusEnergy = []
N, M, K = map(int, input().split())
energy = [ [ 5 for i in range(N)] for j in range(N) ]
tree = [ [ [] for i in range(N)] for j in range(N) ]
plusEnergy = [ [ 0 for i in range(N)] for j in range(N) ]
for i in range(N):
plusEnergy[i] = list(map(int, input().split()))
for i in range(M):
row, col, value = map(int, input().split())
tree[row-1][col-1].append(value)
dieTreeList = []
for i in range(K):
for row in range(N):
for col in range(N):
if not tree[row][col]:
continue
tree[row][col].sort()
if energy[row][col] >= sum(tree[row][col]):
for i in range(len(tree[row][col])):
energy[row][col] -= tree[row][col][i]
tree[row][col][i] += 1
else:
i = 0
while(tree[row][col]):
if i == len(tree[row][col]):
break
if tree[row][col][i] <= energy[row][col]:
energy[row][col] -= tree[row][col][i]
tree[row][col][i] += 1
i += 1
else:
dieTreeList.append([row, col, tree[row][col][i]])
tree[row][col].remove(tree[row][col][i])
for row in range(N):
for col in range(N):
for i in range(len(dieTreeList)):
if dieTreeList[i][0] == row and dieTreeList[i][1] == col:
energy[row][col] += int(dieTreeList[i][2]/2)
dieTreeList.clear()
for row in range(N):
for col in range(N):
if tree[row][col]:
for i in range(len(tree[row][col])):
if tree[row][col][i] % 5 == 0:
if row-1 >= 0 and col-1 >= 0:
tree[row-1][col-1].append(1)
if row-1 >= 0:
tree[row-1][col].append(1)
if row-1 >= 0 and col+1 < N:
tree[row-1][col+1].append(1)
if col-1 >= 0:
tree[row][col-1].append(1)
if col+1 < N:
tree[row][col+1].append(1)
if row+1 < N and col-1 >= 0:
tree[row+1][col-1].append(1)
if row+1 < N:
tree[row+1][col].append(1)
if row+1 < N and col+1 < N:
tree[row+1][col+1].append(1)
for row in range(N):
for col in range(N):
energy[row][col] += plusEnergy[row][col]
answer = 0
for row in range(N):
for col in range(N):
answer += len(tree[row][col])
print(answer)답지를 보기 전에 계속 코드를 리뷰하면서 시간 초과가 날만한 부분을 찾아서 고쳤다.
1차 시도
제일 처음에는 (아직도 왜 그랬는지 모르겠다) 여름을 시작할 때 2차원 배열을 전부 순회하면서 죽은 나무들을 양분으로 넣어줬다.
하지만 굳이 다 돌필요 없고 죽은 나무 자리에다가 값만 넣어주면 된다.
결과는 ? 아직 한참 남았다.
2차 시도
def printTreeFunc():
def printEnergyFunc():코드를 짜면서 중간 중간 맵을 확인해야해서 함수를 만들어 놓고 계속 써먹었다. 이런 함수 선언문들이 들어있으면 시간이 좀 오래 걸릴수도 있겠다? 라는 생각을 했다.
(지금 생각해보면 진짜 어이가 없지만, 얼마나 간절했으면...)
바로 지워주자.
결과는 ? 어림없다.
3차 시도
제일 처음 입력을 받을 때 NxN 크기의 배열을 잡아두고 plusEnergy 값을 채워넣었는데, 그게 아니라 입력 받으면 바로 배열에 바로 append !! 나름의 의미있는 시도였다고 생각한다.
결과는 ? 안돼 돌아가.
4차 시도
그나마 이게 제일 의미있는 시도였지 싶은데.. 아예 정답 코드를 보지 말고 이전에 그랬던 것 처럼 어어어어엄청 쪼끔만 살짝 흘깃 보고 힌트를 얻자!! 라는 생각으로 답지를 스리슬쩍 실눈 뜨고 막 온갖 주접을 다 떨면서 봤다.
코드의 제일 위에 보이는 dx, dy !!!!!!!!!!!!!
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]진짜 정답인줄 알았다.
결과는 ? 아직이야... 중요한, 확실한 뭔가가 딱 하나 빠졌다고ㅠ
dx, dy를 이용하는 방법은 다른 코드들을 봐도 전부 이렇게 쓰더라!! 완전히 내걸로 만들어서 나도 써먹어야겠다.
그렇게 머리를 굴리다가.. 시간을 너무 뺏기는거 같아서 답지를 봤다.
와.......... 진짜 어떻게 이런 생각을 할 수 있는지 모르겠다.
사실상 이 문제의 핵심이었다.
< 봄 - 여름 >을 묶어주는 것!!!!!!!!!
어떻게 이런 생각을 했을까... 아니지 왜 이 생각을 못했을까....
나는 너무나 당연하게 봄과 여름을 다른 프로세스로 나눠주었고 봄에서 죽은 나무들을 다른 배열에 저장해두었다. 나이가 어린 나무부터 양분을 주어야 하니까 ? 자연스레 나무들을 정렬해주었고 나이가 어린 나무가 앞으로 나오게 했다. 그렇게해서 봄에 죽은 나무들은 여름에 양분으로 바뀌어지는 것이다.
하지만 정답 코드는 정말... 어마무시했다.
애초에 번식을 할 때(가을)부터 나이가 1인 나무를 왼쪽에다가 appendleft 해주면 ?
=> List에는 appendleft 가 없으므로 insert(0, 1)
무조건 나이가 어린 나무가 왼쪽으로 가있게 된다.
그렇게되면 나무가 죽어서 양분으로 바뀔 때 다시 2차원 배열을 순회하지 않아도 되고, 정렬을 따로 해주지 않아도 된다.
아마 이 부분에서 시간이 어마무시하게 줄어서 통과가 된게 아닌가 싶다.
그리고 부가적인 부분으로는
/ : 나누기
// : 나누기 연산 후 소수점 이하의 수를 버리고, 정수 부분의 수만 구함
이 차이를 몰랐던 점과 연산을 할 때마다 나무 배열의 길이를 구해주는 것이 아니라 길이를 구해서 변수에 넣어놓고 두고두고 쓰는.. 뭐 이정도?
사실 봄과 여름을 묶어줄 수 있다는 이 어마무시한 사실이 이 문제의 핵심이기에 다른 부가적인 부분은 크게 시간에 영향을 끼치지 않은 듯하다.
정답 코드
energy = []
tree = []
plusEnergy = []
# dieTreeList = []
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
N, M, K = map(int, input().split())
# energy = [ [ 5 for i in range(N)] for j in range(N) ]
energy = [ [5] * N for j in range(N) ]
# 처음에 5로 양분 초기화
tree = [ [ [] for i in range(N)] for j in range(N) ]
# 처음에 나무 초기화
# plusEnergy = [ [ [] for i in range(N)] for j in range(N) ]
for i in range(N):
plusEnergy.append(list(map(int, input().split())))
# 겨울에 추가될 양분 map
for i in range(M):
row, col, value = map(int, input().split())
tree[row-1][col-1].append(value)
# 입력이 2 1 3 이면 tree[1][0] = 3
# def printTreeFunc():
# print("Tree")
# for i in range(N):
# for j in range(N):
# print(tree[i][j], end = ' ')
# print()
# def printEnergyFunc():
# print("Energy")
# for i in range(N):
# for j in range(N):
# print(energy[i][j], end = ' ')
# print()
for aaa in range(K):
# print("봄 시작")
# 봄, 여름 같이
for row in range(N):
for col in range(N):
if not tree[row][col]:
# 나무가 없으면 바로 재껴
continue
lenTree = len(tree[row][col])
# sumTree = sum(tree[row][col])
# print("before sort", tree[row][col])
# tree[row][col].sort()
# 예를 들어서 나무가 2, 1, 5 있다 쳐
# print("after sort", tree[row][col])
for j in range(lenTree):
if energy[row][col] >= tree[row][col][j]:
energy[row][col] -= tree[row][col][j]
# 양분 마이너스
tree[row][col][j] += 1
# 나이 1 증가
else:
# 양분 모자라면 바로 그 때에 대해서 여름
# 모자랐을 때 직전까지는 한거고 모자라자마자 바로 온거니까 바로 pop 하면 되지
# 이게 되는 이유는 새로운 나무를 심을 때 왼쪽으로 insert(0, ) 해주니까 나이가 어린 나무가 무조건 왼쪽
# 그럼 문제의 조건대로 어린 나무부터 순서대로 가지
for k in range(j, lenTree):
energy[row][col] += (tree[row][col].pop() // 2)
break
# if energy[row][col] >= sum(tree[row][col]):
# # 안에 나무들 모두한테 양분을 줄 수 있으면?
# for i in range(len(tree[row][col])):
# energy[row][col] -= tree[row][col][i]
# # 양분 마이너스
# tree[row][col][i] += 1
# # 전부 나이 1 증가
# else:
# # 양분이 부족하면?
# # print("양분이 부족하다. ")
# # printTreeFunc()
# for i in range(len(tree[row][col])):
# if tree[row][col][i] <= energy[row][col]:
# energy[row][col] -= tree[row][col][i]
# # 양분 마이너스
# tree[row][col][i] += 1
# # 그 나무 나이 1 증가
# else:
# dieTreeList.append([row, col, tree[row][col][i]])
# tree[row][col][i] = 0
# # tree[row][col].remove(tree[row][col][i])
# while(0 in tree[row][col]):
# tree[row][col].remove(0)
# i = 0
# while(tree[row][col]):
# # print("tree[row][col] = ", tree[row][col])
# if i == len(tree[row][col]):
# break
# if tree[row][col][i] <= energy[row][col]:
# # 있는 양분보다 나무 나이가 작으면
# energy[row][col] -= tree[row][col][i]
# # 양분 마이너스
# tree[row][col][i] += 1
# # 그 나무 나이 1 증가
# i += 1
# else:
# dieTreeList.append([row, col, tree[row][col][i]])
# tree[row][col].remove(tree[row][col][i])
# # print("row = ", row, " col = ", col, " i = ", i)
# # print("죽는 나무 ", dieTreeList)
# print()
# print("봄이 지나갔다")
# printTreeFunc()
# printEnergyFunc()
# print("여름 시작")
# 여름
# for row in range(N):
# for col in range(N):
# 필요 없음
# for i in range(len(dieTreeList)):
# # print("row = ", row, " col = ", col, " i = ", i)
# # print("추가된 양분 = ", int(dieTreeList[i][2]/2))
# energy[dieTreeList[i][0]][dieTreeList[i][1]] += int(dieTreeList[i][2]/2)
# dieTreeList.clear()
# # print()
# print("여름이 지나갔다")
# printTreeFunc()
# printEnergyFunc()
# print("가을 시작")
# 가을
# for row in range(N):
# for col in range(N):
# if tree[row][col]:
# for i in range(len(tree[row][col])):
# if tree[row][col][i] % 5 == 0:
# if row-1 >= 0 and col-1 >= 0:
# tree[row-1][col-1].append(1)
# if row-1 >= 0:
# tree[row-1][col].append(1)
# if row-1 >= 0 and col+1 < N:
# tree[row-1][col+1].append(1)
# if col-1 >= 0:
# tree[row][col-1].append(1)
# if col+1 < N:
# tree[row][col+1].append(1)
# if row+1 < N and col-1 >= 0:
# tree[row+1][col-1].append(1)
# if row+1 < N:
# tree[row+1][col].append(1)
# if row+1 < N and col+1 < N:
# tree[row+1][col+1].append(1)
for row in range(N):
for col in range(N):
for age in tree[row][col]:
if age % 5 == 0:
for l in range(8):
nx = row + dx[l]
ny = col + dy[l]
if 0 <= nx < N and 0 <= ny < N:
tree[nx][ny].insert(0, 1)
# print()
# print("가을이 지나갔다")
# printTreeFunc()
# printEnergyFunc()
# print("겨울 시작")
# 겨울
for row in range(N):
for col in range(N):
if plusEnergy[row][col]:
energy[row][col] += plusEnergy[row][col]
# print()
# print("겨울이 지나갔다")
# printTreeFunc()
# printEnergyFunc()
answer = 0
for row in range(N):
for col in range(N):
answer += len(tree[row][col])
print(answer)깔끔하게 정리된 코드
energy = []
tree = []
plusEnergy = []
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
N, M, K = map(int, input().split())
energy = [ [5] * N for j in range(N) ]
tree = [ [ [] for i in range(N)] for j in range(N) ]
for i in range(N):
plusEnergy.append(list(map(int, input().split())))
for i in range(M):
row, col, value = map(int, input().split())
tree[row-1][col-1].append(value)
for aaa in range(K):
for row in range(N):
for col in range(N):
if not tree[row][col]:
continue
lenTree = len(tree[row][col])
for j in range(lenTree):
if energy[row][col] >= tree[row][col][j]:
energy[row][col] -= tree[row][col][j]
tree[row][col][j] += 1
else:
for k in range(j, lenTree):
energy[row][col] += (tree[row][col].pop() // 2)
break
for row in range(N):
for col in range(N):
for age in tree[row][col]:
if age % 5 == 0:
for l in range(8):
nx = row + dx[l]
ny = col + dy[l]
if 0 <= nx < N and 0 <= ny < N:
tree[nx][ny].insert(0, 1)
for row in range(N):
for col in range(N):
if plusEnergy[row][col]:
energy[row][col] += plusEnergy[row][col]
answer = 0
for row in range(N):
for col in range(N):
answer += len(tree[row][col])
print(answer)속이 다 후련하네 진짜 ㅡㅡ
