[파이썬] 백준 2579 : 계단 오르기

[파이썬] 백준 2579 : 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 실버 3 DP 접근 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 계단을 한 계단 밟을지, 두 계단을 밟을지를 선택할 수 있다. dp문제를 풀 때..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 13.
• textsms

[파이썬] 백준 8394 : 악수

[파이썬] 백준 8394 : 악수 https://www.acmicpc.net/problem/8394 8394번: 악수 첫째 줄에 회의에 참석한 사람의 수 n (1 ≤ n ≤ 10,000,000)이 주어진다. www.acmicpc.net 실버 4 수학, DP 접근 하나하나 경우의 수를 직접 계산해보면 피보나치 수열로 규칙이 나타난다는 것을 알 수 있다. 문제는 n의 범위가 어마어마하기 때문에 수가 커지면 커질수록 다루는 수가 기하급수적으로 증가한다는 점이다. 시간 초과하지 않으려면 구한 값의 마지막 자리를 미리 넣어주는 방법을 이용해야 했다. 코드 import sys n = int(sys.stdin.readline()) dp = [1] * (n+1) for i in range(2, n+1): dp[i] =..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 12.
• textsms

[파이썬] 백준 1463 : 1로 만들기

[파이썬] 백준 1463 : 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 실버 3 DP 접근 1로 빼거나 2로 나누어지면 2로 나누거나 3으로 나누어지면 3으로 나눈다. 이걸 그대로 구현하면 10을 입력값으로 주었을 때 예외가 생긴다. 위의 방법을 그냥 분기로 구현하면 10 > 5 > 4 > 2 > 1 이렇게 총 4번이 되지만, 10 > 9 > 3 > 1로 총 3번이면 1로 만들 수 있는 방법이 있기 때문이다. 만약 입력 값에서 처음의 3가지 경우를 각각 사용했을 때 구해진 연산 횟수중에 가장 작은 값을 선택할 수 있다면 좋을 것이다. 문제를..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 12.
• textsms

[파이썬] 백준 1003 : 피보나치 함수

[파이썬] 백준 1003 : 피보나치 함수 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 실버 3 DP 접근 문제에서 써져 있는 재귀함수 방법 그대로 날먹하면 시간초과 당한다... import sys zero_cnt = 0 one_cnt = 0 def fibo(x): global zero_cnt global one_cnt if x == 0: zero_cnt += 1 return 0 elif x == 1: one_cnt += 1 return 1 else: return fibo(x-1) + fibo(x-2) t = int(sys.stdin.r..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 12.
• textsms

[파이썬] 백준 13301 : 타일 장식물

[파이썬] 백준 13301 : 타일 장식물 https://www.acmicpc.net/problem/13301 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net 실버 5 수학, DP 접근 그냥 피보나치 수열을 응용한 문제. 입력한 수를 K라고 가정하고, 피보나치 수열을 prime[1]~prime[K]로 구현한다면 문제에서 제시하는 그림은 다음과 같다. 코드 import sys K = int(sys.stdin.readline()) prime = [0]*(K+1) prime[1] = 1 for i in range(2,..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 12.
• textsms

[파이썬] 백준 9625 : BABBA

[파이썬] 백준 9625 : BABBA https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 실버 5 구현, DP 접근 A는 B로, B는 BA로 바꾸는 걸 반복하고, A와 B의 개수를 세어 보았다. A (1, 0) B (0, 1) BA (1, 1) BA B (1, 2) BA B BA (2, 3) BA B BA BA B (3, 5) BA B BA BA B BA B BA (5, 8) 버튼을 처음 누른 뒤의 화면이 B이므로 B가 된 이후부터의 A의 개수는 0..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 12.
• textsms