전체

2225번 파이썬

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 규칙을 찾고 dp를 이용해서 푸는 문제이다. n=1 n=2 n=3 n=4 n= k=1 1 1 1 1 1 k=2 2 3 4 5 6 k=3 3 6 10 15 21 n=1일때는 k의 개수에 따라 경우의 수가 달라지고 k가 1일때는 경우의 수가 한개이므로 전부다 한개이다! 따라서 이 두경우는 모두 초기화를 해주어야한다. 또한, k=2일때도 경우의수가 n+1이므로 이 경우도 같이 초기화를 해준다. 그리고 k,n이 2이상부터 p[k][n]이 p[k-1][n]+p[k][n-1]이라는 것을 알 수 있는데 이건 쉽게 예제로 생각..

16194번 파이썬

이 문제는 아래 문제와 비슷한 문제 방식이다! 2022.03.30 - [백준] - 11052번 파이썬 11052번 파이썬 이 문제는 p[n]과 i가 1부터 n의 절반까지인 p[n-i] + p[i] 중 값이 최대인걸 p[n]에 저장하는 방식을 이용했다. 즉 p[4]의 경우 p[3]+p[1] or p[2] + p[2] or p[4] 중 최대인 값이 p에 저장되는 dp 방법을 이용했.. suminn0.tistory.com 먼저 dp를 이용하기 위해 p 리스트를 만든다 p의 값에는 deepcopy를 이용해 ary값과 동일하게 넣어준다. 그 다음 1부터 n까지 반복해서 i번째 카드와 num-i번째 dp값을 더한 값을 temp리스트에 넣어준다 (예제로 봤을 때 카드 한개가 들어있는 팩ary[0]과 3개의 카드를 구..

4948번 파이썬

이 문제는 소수를 판별하는 방법만 알면된다. 소수를 판별 할때 그 수에 제곱근 값까지 나누었을때 나머지가 0이 아니면 그 수는 소수인 것만 알고 있으면 된다. from cmath import sqrt import sys input = sys.stdin.readline while 1: n = int(input()) if n==0: break cnt=0 for num in range(n+1,2*n+1): if num==1: continue elif num==2: cnt+=1 continue else: check=False for div in range(2,int(num**(1/2))+1): if num%div==0: check=True break if not check: cnt+=1 print(cnt)

2293번 파이썬

이 문제는 저번에 풀었던 동전2 문제랑 비슷한 유형인데 이번에는 동전의 개수가 아닌 경우의 수를 구하는 문제이다. 또한, 경우의 수 중에 중복되는게 있으면 안된다는 조건 때문에 생각을 좀 오래했다. 이 문제는 ary 반복을 돌린다음 1~k까지 반복을 돌렸는데 그 이유는 두 위치를 바꿔서 돌리게 되면 중복되는 경우의 수가 포함되기 때문이다. 그래서 아래 코드처럼 ary 다음에 1~k까지 반복을 했다. 이렇게 하면 예제처럼 1,2,5일 경우 모든 p에 1로만 이루어져있는 경우가 들어가고 그 다음에 2가 포함되는 경우가 들어가게 된다. 그 다음도 마찬가지로 5가 포함되는 경우가 들어가게 된다. 이렇게 되면 경우의 수는 반복되지 않게 된다! ex) 1 / 1,1 / 1,1,1 / 1,1,1,1 / 1,1,1,1..

9461번 파이썬

이 문제는 초기 설정만 하면 규칙이 일정한 문제이다. 규칙은 i 번째 값이 i-1번쨰와 i-5번째를 더한 값이 반복되는 구조이다. 즉 1~5까지는 초기 설정해주고 나머지는 규칙을 이용한 dp를 이용해서 풀면 쉽게 풀리는 문제인것 같다! import sys input=sys.stdin.readline t = int(input()) p=[0 for _ in range(101)] p[1]=1 p[2]=1 p[3]=1 p[4]=2 p[5]=2 for i in range(6,101): p[i] = p[i-1]+p[i-5] for _ in range(t): n = int(input()) print(p[n])

2294번 파이썬

이 문제는 현재 가격에(num)에 동전 종류에 따른 가격(i) 를 더해서 현재 p[num+i]에 저장되어있는 값보다 p[num]+1이 작으면 그 값으로 치환하는 방식을 이용했다. p값을 10001로 치환해준 이유는 k의 최댓값이 10000이며 10000인 경우도 존재할 수 있기 때문에 10001로 설정했다. 그리고 이 문제는 경우의 수가 아니고 최소 동전 개수를 구하는 문제기 때문에 문제를 잘 읽어보고 풀어야한다!! import sys input = sys.stdin.readline n,k = map(int,input().split()) ary = [int(input()) for _ in range(n)] p = [10001 for _ in range(k+1)] p[0]=0 for num in range..

9465번 파이썬

처음에 이 문제를 풀을 때 뜯을려고 하는 스티커의 왼쪽 부분을 전부 다 검사해서(인접 변 제외) max인 값을 현재 스티커 값과 더해서 dp를 만들려고 했는데 답은 잘 나오는데 시간 초과 에러가 떴다..아마 시간 복잡도가 n^2이라 그런것 같다. 그래서 생각한 다른 방법은 만약 첫번째 행의 3번째 스티커를 뜯었다고 가정할때 (보기에선 100값 스티커) 두번째 행의 2번째와 첫번째 dp값 중 최대값만 계산해서 현재 스티커 값에 플러스 해주는 방식이다. 이걸 코드로 나타내면 아래와 같고 이런 방식을 이용하는 이유는 현재 스티커 값을 최대로 뜯을려고 하기 때문에 이웃한 변 다음칸을 뜯는게 효율적이지만 값이 그 옆에꺼가 더 클 경우가 그게 더 효율적일 수 있기 때문이다. 그리고 현재 col-3한 값을 구하는 것..

1920번 파이썬

방법은 1. 리스트에 있는지 전체 돌려서 확인 2. 이분탐색으로 확인 이분탐색 시간복잡도가 O(logn)이기 때문에 시간은 더 적게걸린다! import sys input = sys.stdin.readline n = int(input()) n_ary=list(map(int,input().split())) m = int(input()) m_ary=list(map(int,input().split())) n_ary.sort() ''' for item in m_ary: if item in n_ary: print(1) else: print(0) ''' for item in m_ary: left=0 right=n-1 found=False while left n_ary[mid]: left=mid+1 elif item ..

2133번 파이썬

이 문제는 홀수 일때는 경우의 수가 존재하지 않아서 짝수일때만 확인해주면 된다. 처음에 2일때 경우의 수는 3개이고 4개일때부터는 p[2]*p[2] + 2이다 뒤에 두가지는 다음과 같은 모양이다 이 모양 하나와 반대 모양 총 두가지이다 즉 p[4] = p[2]*p[2] + 2 이다. 6일 경우부터는 경우가 (2,2,2) (4,2) (2,4) (6)인데 앞에 (2,2,2) (4,2) 이 둘은 p[4]*p[2]한 값과 같고 (2,4)는 4의 모양중 전체 가로길이가 4인 두가지 모양의 경우만 계산해주면 된다.(나머지 경유는 앞에 4,2와 동일하기 때문) 즉 p[2]*2이다. 그리고 마지막으로 가로길이가 6인 경우만 계산해주면된다. 가로길이가 6인 경우는 와 반대 모양 총 두가지이다. 8도 마찬가지로 이렇게 반..

14501번 파이썬

이 문제는 처음부터 n번째까지 반복해서 문제를 풀었다. 문제의 원리는 예를 들어 설명하는게 이해가 빠를 것 같다. ex) 1일의 경우 3일이 걸리는 상담이 있는데 코드로 쓰면 num이 1인 경우이고 상담이 완료되는건 idx값이 3이되는 경우이다. 3일차의 최대로 받을 수 있는 금액이 1일차에 3일 상담을 진행해서 받을 수 있는 금액보다 작으면 그 idx에 num-1일까지 받을 수 있었던(1일차 전에 받았던 최대금액) 최대금액에 1일부터 시작해서 받을 수 있는 금액을 더해서 넣어준다. 그리고 마지막으로 p[num]=max를 해준 이유는 idx값이 모든 일 수가 될 수 없는 경우가 있기 때문에 (idx가 3,6,7인 경우 4,5,2,1값은 0이 됨) 현재 값과 전날까지 받았던 최대 금액과 비교해서 더 큰값을..