Algorithm

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이 됨) 현재 값과 전날까지 받았던 최대 금액과 비교해서 더 큰값을..

1699번 파이썬

반복문이 많아서 pypy로 제출했다..! 문제는 해당 숫자보다 낮은 제곱수를 전부 다 구해서(첨에 바로 직전의 제곱수만 구하면 되는 줄 알았는데 그것보다 작은 값도 최소가 될 수 있는 경우가 존재) 그 중 가장 작은 갯수를 가지는 p값에 1을 더해서 p[num]에 저장한다. import sys input = sys.stdin.readline n = int(input()) p = [0 for _ in range(100001)] p[1]=1 if n>=2: p[2]=2 if n>=3: p[3]=3 for num in range(4,n+1): temp=[] for i in range(1,317): k = pow(i,2) if num < k: break temp.append(p[num-k]) p[num]=min..

1912번 파이썬

ary를 deepcopy해서 새로운 리스트 p(dp를 이용하기 위한 리스트)를 만들어준다. 그리고 나서 두번째 인덱스부터 마지막 인덱스까지 이전 dp에 현재 ary의 값을 더한 값이 ary의 본연의 값보다 큰지 확인하고 크면 해당 dp 인덱스를 그 값으로 교체해준다! 그리고 최종적으로 연속된 값이 가장 큰 값을 p 리스트에서 출력해준다. import sys,copy input = sys.stdin.readline n = int(input()) ary=list(map(int,input().split())) p=copy.deepcopy(ary) for idx in range(1,n): if p[idx] < (p[idx-1]+ary[idx]): p[idx]=p[idx-1]+ary[idx] print(max(p))

14002번 파이썬

res=[] for num in ary: if num not in res: res.append(num) 처음엔 모든 인덱스를 한번씩 돌아서 중복되지 않게 res에 추가하고 마지막으로 정렬해서 출력했는데 틀렸다고 떴다.. 아래 코드는 1부터 n-1번째 인덱스까지 dp를 이용해서 p[i]에 최대 수열의 길이 값을 넣는 코드이다. 최소 수열 길이는 1이기 때문에 모든 값을 1로 초기화하고 i를 1부터 n-1까지 반복해서 i번째까지의 수열 중에서 최대 길이가 되는 수열의 길이를 구해준다. ex) {10, 20, 10, 30, 20, 50} 에서 i가 2면 20까지의 수열에서 수열의 길이를 구한다. p[j]에 +1을 해준 이유는 j번째 인덱스가 i 번째 값보다 작고 이는 최대 수열의 길이에 j다음 i가 포함되는 ..