아리의 개발 일상

[백준 파이썬] 2579 계단 오르기문제계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에서 위치한 도착지점까지 가는 게임이다.각 계단에는 일정한 점수가 쓰여 있고 그 계단을 밝으면 점수를 얻게 된다.이때 총점수의 최댓값을 구해야 하면 아래의 규칙을 지켜야 한다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.마지막 도착 계단은 반드시 밟아야 한다.위그림의 예를 가지고 풀어본다면첫 번째 계단 => 두 번째 계단 => 네 번째 계단 => 다섯 번째 계단 밟으면 최댓값이 나온다.  풀이이 문제를 풀기 위해서 해야 할 첫 번째 생..

[백준 파이썬] 2749 피보나치 수 3  처음에는 이게 무슨 골드 2 문제지 하고dp=[0,1]n=int(input())for i in range(2,n+1): dp.append((dp[i-1]+dp[i-2])%1000000)print(dp[n])이렇게 코드를 제출했다 결과는 메모리 초과로 실패하여 문제 조건을 확인하였다입력이 1,000,000,000,000,000,000 작은 n에 대한 피보나치수열인데 메모리 제한이 128MB였다.문제 답을 출력할 때 1,000,000으로 나눈 나머지를 출력한다라고 적혀있었다.이걸 보고 난 반복되는 주기가 발생할겠다고 생각하여 dp=[0,1]n=int(input())for i in range(2,4500000+1): dp.append((dp[i-1]+dp[..

[백준 파이썬]1106 호텔 https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 문제 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다. 형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다. 예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정..

문제 n가지 종류의 동전이 있고 각 동전은 서로 다른 가치를 나타낸다 그 동전을 합이 k 가 되도록 하는 경우의 수를 구한다 단 가각의 동전은 몇개라도 사용할 수 있다 사용한 동전의 구성이 같은데 수선만 다른 경우는 같은 경우이다 입력 첫줄에 n,k 가 주어지고 다음 n개의 줄에 각 동전의 가치가 주어진다 출력 경우의 수를 출력한다 코드 -처음 생각할때 완전 탐색 방식을 생각하여 문제를 풀었다 def msum(count,result): global ans if result >k: return elif result==k: ans+=1 else: msum(count,result+data[count]) if count 1+1, 2 3이 될 경우수는 2=> 1+1+1, 2+1 dp[i-코인의 값]의미는 그 코인..