https://github.com/prtky/JungleBackjoon
해당링크를 들어가면 코드와 주석만 보실수 있습니다.
24번 문제(2628) 종이자르기
먼저 전체 가로세로값, 몇번 자를지, 자르는 방향과 위치를 인풋으로 받아야한다.
3번째 줄부터는 첫 요소는 0이면 가로 1이면 세로이다.
대략적인 흐름은 알겠다. 그런데 중간에 자른 선과 자른 선 사이의 길이는 어떻게 구해야하는지 모르겠다.
x, y = map(int,input().split()) # 전체 종이 크기를 지정합니다.
cut = int(input()) # 첫 째줄 전체 길이, 자르는 횟수를 받습니다.
width_cuts = [0, x] # 가로 방향 점선
height_cuts = [0, y] # 세로 방향 점선
for _ in range(cut): # 자른 횟수 만큼 반복
arrow, position = map(int, input().split()) # 0과 1로 가로인지 세로인지 판단
# 여기서 주의해야되는 것이 있는데, 0이 가로고 1이 세로이지만
# 세로로 자르는 선은 가로에 영향을 주고, 가로로 자르는 선은 세로에 영향을 준다.
# 이점을 유의해서 설계해야한다. 그림을 그리면 이해하기 편하다.
if arrow == 1: # 세로선일시 가로에 영향을 준다.
width_cuts.append(position)
if arrow == 0: # 가로선일시 세로에 영향을 준다.
height_cuts.append(position)
# 이제 여기서 받은 요소들을 오름차순으로 정리해서 그 차이중 제일 큰 값 추출해서 곱하기.
width_cuts.sort()
height_cuts.sort()
# 이제 리스트의 앞뒤 값의 차이를 구해야하는데, 어떻게 해야할지 몰라서 GPT의 도움을 받았다.
# GPT는 zip이라는 리스트안에서 세트를 묶을수 있는 새로운 함수를 소개해줬다.
max_width_cuts = max(b - a for a,b in zip(width_cuts,width_cuts[1:])) # 넓이 리스트의 있는 값의 앞뒤 값을 빼서 차이가 제일 큰 것을 추출한다.
max_height_cuts = max(b - a for a,b in zip(height_cuts,height_cuts[1:]))
print(max_height_cuts * max_width_cuts) 맨 마지막 zip함수를 몰라서 요소사이의 차이를 구하는 방법을 몰라 헤멧다.
그리고 그림을 그려서 그나마 이해하기 좋았지만 세로로지나가는 자르는 선은 전체 종이에 가로에 영향을 주고 가로는 전체 종이에 세로에 영향을 준다는 점을 유의해야되지 않을까싶다.
각 위치값을 리스트화 시켜서 비교하는 것도 신박한 방법인 것 같다.
이거 푸는데 단계별로 한다고 3시간 쓴게 슬픈 사실이다…
25번 문제(10872) 팩토리얼
팩토리얼은 for문을 통해 구현가능할 것 같다. 인풋 받은 N 값을 1부터 차례로 1씩 올리며 곱하면서 N 값까지 구하면 된다.
N = int(input())
F = 1
for i in range(1, N+1): # 1부터 N까지 모든 요소(i)를 곱합니다.
F *= i
print(F)
# 책이나 인터넷 자료를 찾아보니 팩토리얼을 구하는 방식이 다양하다.
# 본인을 다시 호출하는 재귀함수를 사용한 방법도 있다.
def factorial(n):
if n > 1:
return n * factorial(n-1)
else:
return 1
# 리턴 1에 의해 위로 넘어가고 1*1, 2*1, 3*2 ,4*6 ... 이런식으로 다시올라가서 재귀함수로 팩토리얼을 구현한다.
n = int(input()) # 입력 받기
print(factorial(n)) # 팩토리얼 계산 후 출력26번 문제(1914)하노이 탑
대망의 하노이탑 문제이다. 어렵기로 팀원분들 사이에서 악명이 자자하다.
어릴때 많이해봐서 규칙은 아는데 이걸 프로그래밍하라니…
하노이 탑 자체의 규칙은 굉장히 간단하다. 근데 일정한 규칙이 뭔지 모르겠다. 먼저 옮긴 횟수 K를 구해야한다. 그래서 단계층별 옮기는 횟수를 분석해봤다. N당 최소이동횟수를 구해보면 수식이 2^N-1이 나온다.
def hanoi(n, start, end, via):
if n == 1:
print(start, end) # 원판을 직접 이동
return
hanoi(n - 1, start, via, end) # N-1개를 보조 기둥(via)으로 이동 해당 내용이 재귀되서 프린트가 된다.
# 내가 여기서 이해를 잘못한게 있는데, 함수의 첫째요소가 시작점이고 둘째요소가 목적지이다. 세번째요소는 보조인셈.
print(start, end) # n-1을 보조지점으로 옮겼으니 가장 큰 원판을 목표 기둥(end)으로 이동하고 프린트한다.
hanoi(n - 1, via, end, start) # N-1개를 목표 기둥으로 이동한다. 재귀되서 프린트가 된다.
n = int(input())
K = ((2 ** n) -1) # 최소 이동횟수이다.
print(K)
if n <= 20:
hanoi(n, 1, 3, 2)해당문제를 해석하는데에만 몇시간이 걸리고 최종적으로 8시간정도 사용한 것 같다. 코드보면 엄청 간단해 보이는데, 이 코드 이해하는데만 한세월 걸렸고, 여러 사람에게 물어보면서 이해했다. 아직까지도 한 70퍼만 이해한 느낌이다. 재귀함수 부분의 개념을 더 명확히 알아봐야겠다.
