본문 바로가기

PS/백준46

[테스트케이스 추가] 백준 10844 번: 쉬운 계산 수 python, 파이썬 1. 문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이 마지막 숫자가 무엇인지에 대한 정보도 필요해서 차원을 하나 늘려 기록해야한다. 마지막 숫자가 0이면 1로 증가시키는 방법밖에 없고 마지막 숫자가 9이면 8로 줄이는 방법 밖에 없다. 3. 구현 import sys # sys.stdin=open('input.txt') from collections import deque mod = 10**9 N=int(sys.stdin.readline()) mm=[[0]*10 for _ in range(N+2)] mm[1]=[0,1,1,1,1,1,1,1,1,.. 2021. 7. 19.
[테스트케이스 추가] 백준 1699 시간초과 해결 python 1. 문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 2. 풀이 동전2랑 유사한 문제. 제곱의 수들을 미리 만들어 놓는 게 좋고, 시간복잡도 때문에 min 비교를 i 마다 해야 시간초과를 피할 수 있다. 3. 구현 import sys import math #sys.stdin=open('input.txt') N=int(sys.stdin.readline()) mm=[math.inf]*int(N+2) #최.. 2021. 7. 16.
[테스트케이스 추가] 백준 2294 동전2 python, 파이썬 1. 문제 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 2. 풀이 입력되는 동전의 길이가 많이 길이 않아서 동전 전체를 돌면서 확인해보면 되는 문제 3. 구현 import sys import math # sys.stdin=open('input.txt') n,k = map(int, sys.stdin.readline().split()) coins=[] while n: n-=1 c = int(sys.stdin.rea.. 2021. 7. 15.
[테스트케이스 추가] 백준 9465: 스티커 python, 파이썬 1. 문제 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 2. 풀이 다음 두 가지 경우를 포함시켜 주면 된다. n 번째 아랫줄의 최댓값은 (n-1 윗줄 or n-2 두 개 중 최댓값) + n번째 아랫줄의 value 3. 구현 import sys sys.setrecursionlimit(10**8) sys.stdin=open('input.txt') T= int(sys.stdin.readline()) def dp(r,n, mm, lis).. 2021. 7. 8.
반응형

티스토리툴바