하나씩 알아가기

인접한 두 사탕을 교환하여 그 때마다 사탕 길이를 계산하고 가장 긴 사탕 길이를 출력하면 해결할 수 있는 문제입니다. 양옆에 인접한 사탕을 스왑하고 가로 길이 확인 -> 갱신 세로 길이 확인 -> 갱신 스왑한 사탕을 되돌려 놓음 위아래로 인접한 사탕을 스왑하고 가로 길이 확인 -> 갱신 세로 길이 확인 -> 갱신 빨간 글씨로 쓴 부분은 반복되기 때문에 함수로 빼 주었습니다. 길이를 계산해 주는 함수에서 중요한 것은 내부 루프입니다. index가 범위를 벗어나지 않도록 0 ~ n-1(n-1미포함)까지 설정 해주고 인접한 두 사탕이 같은 사탕이면 count를 증가시켜 주고 다른 사탕이면 길이를 갱신하고 다음번 비교를 위해 count를 1로 초기화 시킵니다 파이썬의 함수 내부에 global 키워드를 사용하면 ..

E, S, M 은 각각의 범위를 가지고 있습니다. 그리고 그 범위를 넘어가면 1로 초기화 시켜주는 규칙만 지켜주며 전체를 카운트 해주는 변수를 결과로 출력해주면 됩니다. e, s, m = map(int, input().split()) year = 0 esm = [0, 0, 0] while esm[0] != e or esm[1] != s or esm[2] != m: year += 1 esm[0] += 1 esm[1] += 1 esm[2] += 1 if esm[0] == 16: esm[0] = 1 if esm[1] == 29: esm[1] = 1 if esm[2] == 20: esm[2] = 1 print(year) www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라..

틀린 부분이 있을 경우, 지적해 주시면 감사하겠습니다. 아홉 개의 input이 들어오는데 이 중 두 개의 input은 fake고, 일곱 개의 input의 합이 100인 것들만 오름차순으로 출력하면 되는 간단한 문제입니다. 브루트 포스(Brute Force) 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 문제를 해결하는 방법 브루트 포스라 이름은 거창한데 원시적인 방법으로 문제를 풀어야 할 경우 사용하는 것 같습니다. 그런데 모든 문제에서 사용되지 않나요?.. 사실 이런 용어가 잘 와닿지는 않네요ㅠ 조금 더 내공이 쌓이면 어떤 경우에 브루트 포스 방법이 사용되는 지 파악이 되는 날이 오면 좋겠네요 문제로 돌아와서 9개의 데이터 중 2개의 데이터만 뽑아서 100이 되면 출력하는 식으로 문제를 풀겠습..

문제를 해결하기 위한 점화식을 구하려면 2차원 dp를 만들어야 합니다. dp[n][1] = dp[n-1][2] + dp[n-1][3] dp[n][2] = dp[n-2][1] + dp[n-2][3] dp[n][3] = dp[n-3][1] + dp[n-3][2] n을 만들기 위한 방법의 수 중 1로 끝나는 경우를 dp[n][1]이라고 합시다. dp[n][1]은 ~~~ + 1 이런 식입니다. dp[n-1][?] 의 경우 1로 끝날 수 없기 때문에 2나 3이 올 수 밖에 없기 떄문에 dp[n][1] = dp[n-1][2] + dp[n-1][3]가 성립합니다. 그리고 dp[n][2]의 경우 주의해야 할 점은 ~~~ + 2로 끝났기 때문에 dp[n-2][?] 이 와야 한다는 점입니다. ※반복문 내부의 점화식에 %1..

정수 n을 입력 받아서, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제입니다. 1, 2, 3이라는 숫자가 고정이 되어 있습니다. 규칙을 찾아봅시다. n 1 2 3 4 5 경우의 수 1 2 4 7 ? 네번째 까지 구한 결과 f(1) + f(2) + f(3) = f(4)가 성립합니다 다섯번째 까지만 수동으로 구해봅시다 11111 1112 1121 1211 2111 122 212 221 113 131 311 23 32 총 13가지입니다. f(2) + f(3) + f(4) = f(5) 가 성립하므로 f(n) = f(n-3) + f(n-2) + f(n-1) 로 점화식을 도출할 수 있습니다. dp = [0 for _ in range(11)] dp[1] = 1 dp[2] = 2 dp[3] = 4 fo..

점화식을 찾아봅시다. 그림을 보고 입력받은 수가 n이라 할 때, n-2번째 까지의 경우는 두 가지이고 n-1번째 까지의 경우는 한 가지입니다. 좀 더 자세히 말하면 n-2번째까지 타일이 채워진 경우에서 너비가 2인 블럭으로 채우면 n번째 항까지 채운 경우가 되고 n-1번째 까지 타일이 채워진 경우에서 너비가 1인 블럭으로 채우면 n번째 항까지 채운 경우가 되는 것입니다. 그래서 f(n) = 2 * f(n-2) + f(n-1) 이렇게 점화식을 구할 수 있습니다. n = int(input()) dp = [0 for _ in range(1001)] dp[0] = 0 dp[1] = 1 dp[2] = 3 for i in range(3, n+1): dp[i] = 2 * dp[i-2] + dp[i-1] print(d..

그림을 그려가면서 가로의 길이에 대해 몇 가지의 방법으로 타일링을 할 수 있는지 구해봅시다 가로의 길이 1 2 3 4 방법의 수 1 2 3 5 점화식이 피보나치 수열처럼 이루어지는 것을 알 수 있습니다. f(n) = f(n-2) + f(n-1) (n>2) 위의 테이블대로 dp테이블을 구현해준다는 생각으로 코드를 짜겠습니다. n = int(input()) dp = [0 for _ in range(1001)] dp[1] = 1 dp[2] = 2 for i in range(3, n+1): dp[i] = dp[i-2] + dp[i-1] print(dp[n]%10007); 조금만 잘못 짜면 IndexError가 발생할 수 있으니 주의해야합니다. 결과로 특정 수와 나눈 나머지를 출력하라고 요구하는 이유는 결과값이 ..

10을 세 가지 연산을 이용하여 1로 만든다고 할 때 모든 경우 중에 가장 작은 수를 찾아내야 합니다. 10 -> 9 -> 8 -> 7 -> ... -> 1 (x) 10 -> 9 -> 3 -> 1 (o) * 점화식: 수열의 각각의 항들의 관계를 나타낸 식 모든 경우의 수를 고려할 경우 점화식을 떠올리는 방법을 생각해 내는 것이 좋은 방법이 될 수 있습니다. 이 문제의 경우 수를 줄일 수 있는 연산은 세 가지 밖에 없으므로 점화식은 이 경우를 포함하여 적어줘야 합니다. f(n) = 1 + min(f(n/3), f(n/2), f(n-1)) 그런데 가령, f(n/3)이 반드시 존재하는 값은 아닐 수 있지만 이렇게 점화식 형태로 표현이 가능한 경우 다이나믹 프로그래밍을 적용하여 문제를 해결하는 것이 가장 일반적..