본문 바로가기
[백준][파이썬] 1182 부분수열의 합 핵심 1. visited 사용할때 not in stack 이 두개의 차이는 중복된 숫자를 체크 가능한지 여부이다. 2. depth를 다르게 줘야할때는 함수 밖에서 depth를 다르게 설정해서 줄 수 있다. N, S = map(int, input().split()) lit = list(map(int, input().split())) count = 0 visited = [False] * N def per(idx, depth, stack, max): global count if depth == max: total = 0 for sum in stack: total += sum if total == S: count += 1 for i in range(idx, N): if visited[i] ==False: vis.. 2021. 1. 18.
[백준][파이썬] 6603 로또 6603번 제출 맞은 사람 숏코딩 재채점 채점 현황 내 제출 난이도 기여 강의 질문 검색 로또 성공출처다국어분류 한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 128 MB 28282 15492 10423 53.921% 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21],.. 2021. 1. 15.
[백준][파이썬] 2529번 부등호 부등호 성공출처분류 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 256 MB 10238 5175 3618 49.024% 문제 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. A => 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 3 1 7 0 이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이.. 2021. 1. 9.
[백준][파이썬] 14425 부분수열의 합(2) [핵심] 1. 부분수열의 합(1) 과 같이 수열을 재귀함수를 통해서 생성한다 2. check라는 boolean형 리스트를 만들어주고, SUM(수열) 을 통해서 해당 숫자를 True로 설정한다 3. False(즉 나오지 않은 수열의 합) 중 가장 작은 수를 출력하다 시간이나 메모리가 괜찮으려면? 모두 저장할 필요는 없고, sum(수열)이 기존의 수보다 크다면 저장안하고 버려도 된다. n = int(input()) numlist = list(map(int,input().split(" "))) numlist.sort() visited = [False for i in range(n)] check = [1] + [0 for j in range(2000000)] def recu(limit,cnt,lit,space,.. 2020. 9. 26.
[백준][파이썬] 11053 가장 긴 증가하는 부분 수열 아래의 블로그를 참고했다. 앞에있는 숫자중 나보다 작은 수들중 길이가 최고인것의 +1 ... num = int(input()) numlist = list(map(int,input().split())) dp = [0 for i in range(num)] for i in range(num): for j in range(i): if numlist[i] > numlist[j] and dp[i] 2020. 8. 3.
[백준][파이썬] 2193번 이친수 규칙은 N-2번째까지의 합 + N0000 의 경우의 수를 합친것이였다. N = int(input()) #담을 공간 생성 numlist = [0 for i in range(91)] #초기값 설정 numlist[1] = 1 numlist[2] = 1 numlist[3] = 2 #규칙 찾기 for i in range(4,N+1): tem = 0 for j in range(i-1): tem += numlist[j] numlist[i] = tem+1 print(numlist[N]) 2020. 7. 28.
[백준][파이썬] 11057 오르막 수 쉬운 계단 수 문제와 거의 동일한 문제다. N = int(input()) #각 수마다 10개씩 값을 갖는다 dp = [[0 for i in range(10)] for j in range(1001)] #첫 시행 초기화 for i in range(0,10): dp[1][i] = 1 #점화식 규칙 for i in range(2,N+1): for j in range(10): tmp = 0 for k in range(j+1): tmp += dp[i-1][k] dp[i][j] = tmp print(sum(dp[N]) % 10007) 2020. 7. 28.
[백준][파이썬] 10844 쉬운 계단 수 DP는 결국 점화식을 찾고 점화식을 어떻게 배열에 저장해줄지 결정하면 된다. N = int(input()) #각 수마다 10개씩 값을 갖는다 dp = [[0 for i in range(10)] for j in range(101)] #첫 시행 초기화 for i in range(1,10): dp[1][i] = 1 #카운팅 0, 9,1~8 은 규칙이 다른것을 생각하자 for i in range(2,N+1): for j in range(10): if j == 0: dp[i][j] = dp[i-1][1] elif j == 9: dp[i][j] = dp[i-1][8] else: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] print(sum(dp[N]) % 1000000000) https:/.. 2020. 7. 28.
[백준][파이썬] 1,2,3 더하기 규칙을 찾는 연습을 잘하자.. 규칙을 논리적으로 찾을 수 있다면 좋다. 하지만 그것이 어려울 경우에는 무조건 숫자를 나열해보면서 찾는 것도 하나의 방법이다. case = int(input()) for _ in range(case): num = int(input()) numlist = [1,2,4] for i in range(3,num): tem = numlist[-1]+numlist[-2]+numlist[-3] numlist.append(tem) print(numlist[num-1]) 2020. 7. 21.

티스토리툴바