꾸준한 연습장

1082번: 방 번호스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이고, M원을 모두 사용해www.acmicpc.net 문제스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이다.문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 Pi이다. 문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 원하는 만큼 숫자를 구매할 수 있다. 방 번호가 0이 아니라면 0으로 시작할 수 없다.예를 들어, N = 3, M ..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr ↓ 문제 열기더보기   풀이 제한사항 100,000 및 타일 문제이므로 DP를 활용해야 함을 쉽게 유추할 수 있다.어떤 점화식을 도입할 수 있을지 살펴보도록 하자.  tops 의 원소가 하나 추가될 때, 회색 부분은 기존(dp[n-1])의 모든 경우의 수가 고려된 부분이므로 흰 부분에 대해서 타일링을 채우는 방법을 고민해야 한다. 흰 부분은 다음과 같은 방법으로 채울 수 있다.  따라서 tops에 따라 총 3가지 경우의 수로 구분할 수 있다(현재 고려할 top 이 0이라면, 세 번째 경우는 제외하면 된다).  하..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   풀이 2 x n 의 공간이 주어질 때 2 x 1 의 타일을 놓는 경우의 수를 구해야 하는 동적 계획법 문제이다.n이 1 증가할 때 타일을 놓는 방법은 다음과 같다. dp[n]일 때의 경우에 세로로 타일을 놓는다dp[n-1]의 경우에 가로로 2칸짜리 타일을 놓는다 따라서 점화식은 dp[n] = dp[-1] + dp[-2] 이다. def solution(n): dp = [0, 1, 2] for i in range(n - len(dp) + 1): dp.append((dp[-1] + dp[-2..