본문 바로가기

Python45

[알고리즘][백준] 17103번 골드바흐 파티션 - 파이썬(python) 풀이 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 1 = 1 2 = 3 3 = 5 = 2*1 + 3 4 = 11 = 2*3 + 5 5 = 21 = 2*5 + 11 8 = 171 12 = 2731 직접 그려보면서 위와 같은 규칙을 발견했다 import sys n = int(sys.stdin.readline()) dp = [0] * 1001 dp[1] = 1 dp[2] = 3 for i in range(3, n+1): dp[i] = dp[i-1] + 2*dp[i-2] print(.. 2024. 3. 5.
[알고리즘][백준] 11726번 2×n 타일링 - 파이썬(python) 풀이 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 타일 개수를 구해보면 결국 피보나치 수열을 구하는 문제이다 import sys n = int(sys.stdin.readline()) dp = [0] * (n+1) dp[1] = 1 dp[2] = 2 ''' 1 = 1 2 = 2 3 = 3 4 = 5 5 = 8 ''' for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[n] % 10007) 이렇게 하니 런타임에러가 발.. 2024. 3. 5.
[알고리즘][백준] 1463번 1로 만들기 - 파이썬(python) 풀이 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 단순하게 3의 배수로 만들고 진행하면 되겠다 싶어서 아래와 같이 코드를 작성했는데 import sys n = int(sys.stdin.readline()) cnt = 0 ''' 10 → 9 → 3 → 1 10 → 5 → 4 → 2 → 1 10 11 12 15 ''' while n != 1: if n % 3 == 1: n -= 1 n //= 3 cnt += 2 elif n % 3 == 2: n -= 2 n //= 3 cnt += 3 elif n % 3 == 0: n //= 3 cnt += 1 elif n % 2 .. 2024. 3. 4.
[알고리즘][백준] 17103번 골드바흐 파티션 - 파이썬(python) 풀이 https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 6588번 골드바흐의 추측을 응용한 문제이다 1,000,000개의 수를 매번 소수인걸 확인하기엔 메모리사용이 엄청나기 때문에 먼저 에라토스테네스의 체를 사용하여 소수를 구별한다. import sys t = int(sys.stdin.readline()) sosu = [True] * 1000001 for i in range(2, int(len(sosu)**0.5)+1): if sosu[i]: for j.. 2024. 3. 3.

티스토리툴바