파이썬

2xn 크기 직사각형을 채우는 방법의 수를 구하는 문제이기 때문에 숫자가 매우 커지게 되므로 10007로 나눈 나머지를 출력해야 한다.피보나치 수열과 비슷한 구조로 해결할 수 있는데, 이 타일링 방법의 규칙을 분석해보면 다음과 같다.  f(n) = f(n-1) + f(n-2) f(n-1) : 2x1 크기의 타일을 세로로 하나 추가한 경우f(n-2) : 1x2 크기의 타일을 두 개 추가한 경우  최소가 n-2 이기 때문에 각각 f(1)과 f(2)의 초깃값을 부여해야 한다.2x1 직사각형을 채우는 방법은 1가지 이므로 f(1) = 1 , 2x2 직사각형을 채우는 방법은 2가지 이므로 f(2) = 2 이다. 따라서 최종적으로 결과는 f(n) % 10007 인 셈! ++ 여기서 굳이 다른 숫자도 아니고 1000..

import sys N, M = map(int, input().split())arr = list(map(int, sys.stdin.readline().split()))for _ in range(M): i, j = map(int, input().split()) print(sum(arr[i-1:j])) 처음에 작성했던 코드이다.예제로 테스트해본 결과 정답은 올바르게 나오지만, 아무래도 합계를 구하는 sum(arr[i - 1 : j]) 부분의 시간 복잡도가 매우 커지는 경우가 있게 되어 시간초과 오류로 틀렸음매번 구간 합을 계산하기 위해 sum(arr[i - 1 : j]) 을 호출하여 M 번의 구간 합을 계산해야 하기 대문이다. 이 문제를 해결하기 위해 찾아보니 구간 합 배열 (누적 합)을 구현, ..

다국어 문제이므로 이해를 위해 예시를 통해 짧게 설명을 해보자면 다음과 같다. N 으로 4가 주어지면 4명의 사람이 있는데, 이들이 각각 1 3 1 4 라는 의미는 각각 자신이 필요한 피자의 갯수이며 피자는 1번 사람부터 순서대로 1초마다 제공된다. 따라서 힌트에 나와있는 것처럼 피자를 받는 사람 번호를 일일이 기록해보면1 2 3 4 2 4 2 4 4 가 되고,여기서 각자 마지막으로 피자를 받은 순간이 피자 수령을 완료한 시점이기 때문에 결과는 1 7 3 9 가 되는 것이다!(각 숫자마자 제일 나중에 나온 인덱스+1 을 결과로 하여 출력하는 셈)  N = int(input())A = list(map(int, input().split())) # 1 3 1 4pizza = {i + 1 : A[i] for i..

스택을 활용하는 문제로, 첨부된 그림에 나타난 것처럼 정식 줄이 있고 그 옆에 임시 저장소 같은 골목길 이렇게 두 공간이 존재하는 상태이기 때문에 스택을 두 개 활용해주면 된다.  접근 방법: 큐와 스택을 활용- 줄 서있는 사람들을 기존의 arr 스택의 앞에서부터 차례대로 꺼내면서, 카운터에 바로 갈 수 없는 사람은 임시 스택 temp에 저장해두는 방식 - 현재 사람들이 가져야 할 번호표가 1번부터 시작해 순차적으로 카운터에 도달해야 한다.- 만약 arr 줄에서 나오는 번호와 번호표가 맞지 않으면 임시 스택 temp에 해당 사람을 보관했다가 나중에 꺼내기!- 이때 temp 스택에서 번호를 확인하는 조건은 맨 위의 번호가 현재 필요한 번호와 일치한다면, 해당 번호의 사람을 꺼내서 카운터로 전달하고 필요한 ..

얼핏 보기엔 쉬워보이지만 "괄호를 적절히 쳐서 이 식의 값을 최소로 만든다" 는 개념을 정확히 이해하고 구현 방법을 떠올려야 풀 수 있는 문제였다.결론적으로 말하면 식을 최소로 만드는 방법은 입력식에서 - 기호를 기준으로 사이에 있는 숫자들을 모두 더해서 빼주면 된다는 뜻이다. 예를 들어 55 - 10 + 20 - 30 + 40 + 50 와 같은 식이 주어졌다고 가정해보자.이 상태에서 괄호를 적절히 쳐서 최소값을 만들어 내는 것이 목표이다. 뺄셈 하는 방법을 다시 생각해보면 100 - 30 보다 100 - 70 이 더 작은 것과 같이, 최솟값은 빼는 숫자가 최대일수록 결과값을 작아져서 최솟값이 완성되는 것이다.즉 같은 말을 더 구체화 해보자면 100 - (2 + 18) 보다 100 - (40 + 30) ..

import sysN, K = map(int, input().split())money = list(map(int, sys.stdin.read().splitlines()))cnt = 0for m in money[::-1]: if(m > K) : continue cnt += (K//m) K = K % m if(K == 0): breakprint(cnt)  - 동전들이 오름차순으로 차례대로 주어졌기 때문에 이를 고려하여 입력받은 동전 리스트를 역순으로 만들어서 for 문에 넣었음 - 최소 동전 개수를 저장하기 위한 cnt 라는 변수를 생성 => 이를 이용해서 반복문에서 계산식 저장- K가 목표하고자 하는 금액이고, 반복문에서의 m은 보유하고 있는 동전 (큰 금액부터 하나씩) 이므로 m이 ..