![]()
말만 번지르르하지 별거 없다. 파란 영역 중에 제일 큰 계단을 찾으라는 문제. 아직 스위핑을 안배워서 기본 점수만 받아 보았다. 경우에 따라 잘 나눠서 코딩해주면 된다. 1. 이전값 보다 큰 경우 이전 dp값 +1 2. 이전값과 같은 경우 이전 dp + 0 3. 이전값보다 작을 경우 이전 dp값이 현재 높이보다 작은 경우 : 이전 dp+1 이전 dp값이 현재 높이와 같은 경우 : 이전 dp +0 이전 dp값이 현재 높이보다 클 경우 : 현재 높이값 n=int(input()) h=[0] h.extend(map(int,input().split())) dp=[0 for _ in range(n+1)] dp[1]=h[1] for x in range(1,n+1): if h[x]>h[x-1]: dp[x]=dp[x-1..
![]()
0부터 n까지의 정수 k개를 더해서 n이 되는 경우의 수를 구하는 프로그램 뭔가 고등학교 시절의 자연수 분할이 떠오른다. 차이점은 0도 포함한다는 점 예를들어 0부터 9까지 2개로 나타내면 0+0 1+0, 0+1 2+0, 1+1, 0+2 3+0, 1+2, 2+1, 0+3 4+0, 1+3, 2+2, 3+1, 4+0 5+0, 1+4, 2+3, 3+2, 4+1, 5+0 ... 와 같이 (n,2)=n+1임을 알 수있다. 그리고 잘 보면, 1+ n-1, 2+n-2꼴로 나타 낼 수 있는데, 이를 잘 보면 (n,k)=(n-1,k-1)+(n-1,k-2)...(n-1,0)으로 나타낼 수 있음을 알 수 있다. 가로는 숫자, 세로는 k개로 나타 낸 것이다 0 1 2 3 4 1 1 1 1 1 1 2 1 2 3 4 5 3 1 ..
![]()
캡틴 이다솜 문제를 고민하기에 앞서 사면체에 들어가는 대포알의 갯수를 고민해 보자. 1개, 4개, 10개, 20개... 다음은? 우선 밑면을 생각해 봤을때, 밑면에 추가되는 삼각형이 점점 커짐을 알 수 있다. n이 300,000이라고 해서 300,000까지 다 구해놓기에는 우리에게 주어진 자원은 한정적이므로, 다른 방식으로 구해보자. 결국 우리는 n보다 같거나 많은 양의 대포가 쌓여있는 사면체가 처음 등장하기까지 구해야 한다. 그러므로, 이렇게 세울 수 있다. n=int(input()) tri=[1,3] d=[1,4] idx=1 while n>d[-1]: idx+=1 tri.append(tri[idx-1]+(tri[idx-1]-tri[idx-2])+1) d.append(d[idx-1]+tri[idx]) ..
