1. 풀이 제일왼쪽열, 제일 위쪽 행의 값이 주어지고, 다른 자리는 왼,왼위,위 중 가장 큰 수가 들어오면 되는 조건을 보면 아래와 같은 점화식이 만들어진다. L[i][j]=max(L[i-1][j],L[i-1][j-1],L[i][j-1]) 위의 점화식을 만든것 만으로 뭔가 대단한걸 생각해낸 것 같아서 정답인줄 알았지만 시간초과이다. (N=1,000,000) 핵심은 주어지는 왼쪽열, 위쪽행의 값들이 순차적으로 커진다는 것이다. 즉 점화식의 결과는 반드시 아래와 같아진다는 것이다. max(L[i-1][j],L[i-1][j-1],L[i][j-1])=L[i-1][j] 그러니까 0열을 제외한, 즉 1열보다 뒤에 있는 모든 행들은 0행의 값들을 그대로 받을 수 밖에 없다. 따라서 0열과 0행을 다 누적해서 더해주고..

1. 첫번째 풀이 당연히 아래처럼 itertool써서 모든 조합을 전부 구하면 그냥 짜면 시간초과가 난다 from itertools import combinations N=int(input()) L=list(map(int,input().split())) ans=0 for i in range(2, N+1): comb=list(combinations(L,i)) for tup in comb: ans+=max(tup)-min(tup) print(ans) 2. 두번째 풀이 문제에서 주목할 점은 "가장 큰 수"와 "가장 작은수"의 차 만을 구해주면 된다는것. 따라서 숫자를 두개씩 뽑아서 하나는 가장 큰수, 하나는 가장 작은수 로 두고, 그 사이의 숫자의 개수만큼 경우의 수를 곱해주는 식으로 구한다. 아래의 예를 통..

1. 풀이 처음엔 아래와 같은 경우의 수만 생각했지만, 이는 일직선상에서만 적용되는 경우였다. (소스코드1) 즉 2차원의 경우엔 아래와 같은 예외가 존재한다. 따라서 2차원의 좌표평면의 경우는 아래와 같은 경우의 수를 생각할 수 있다. 2. 소스코드 (1) 소스코드1 (경우의 수 오류) import math X,Y,D,T=map(int,input().split()) L=math.sqrt(X**2+Y**2) if L>=D: jump=L//D print("%.10f"%min(jump*T+L-(jump*D),(jump+1)*T)) else: print("%.10f"%min(L,T+D-L,2*T)) (2) 소스코드2 import math X,Y,D,T=map(int,input().split()) L=math.s..

1. 풀이 nCm의 뒤에 0의 개수는 10이 곱해준 수와 같다. 따라서 nCm=n!/(m! * (n-m)!) 에서 10이 몇번곱해졌는지를 확인한다. (1) 10이 몇번곱해졌는지 알기위해선 소인수분해를 이용해 2와 5가 몇번곱해졌는지를 확인한다. (2) n!에서 num가 몇번곱해졌는지는 다음의 방법으로 알 수가 있다. ex) 150! 에서 5가 몇번곱해졌는가? 5^1이 곱해진 횟수를 구한다 => 150//5=30 5^2이 곱해진 횟수를 구한다 => 150//25=6 5^3이 곱해진 횟수를 구한다 => 150//125=1 총 횟수 => 36 이를 소스코드로 나타내면 다음과 같다 def cntNum(a,num): ans=0 multiNum=num while(multiNum

1. 풀이 (1) 0열(빵집)에서 가장 윗 행부터 차례대로 출발하여 (오른쪽위,오른쪽,오른쪽아래) 순서대로 파이프를 놓는다. (2) 끝열(원웅이집) 까지 놓을 수 있으면 최종답 +1후 종료, 놓을자리가 없으면 그자리에서 종료 (3) 이때 방문했던 곳은 다시 방문할 수 없으므로 표시해준다. (끝열(원웅이집)까지 못가더라도 윗행에서 못가면 아래에서도 못가기 때문에 visited로 표시해준다) * 파이프를 최대한으로 설치하기 위해선 무조건 (우상,우,우하) 순으로 진행되고, 윗행에서 부터 아래행으로 내려오면서 탐색하면 반드시 최적해가 나오는 그리디 문제이다. 또한 파이프를 최대로 만들기 위해선 엇갈리는 경우도 배제해야 한다. ( 커플만들기 문제와 비슷 https://sosoeasy.tistory.com/40)..

1. 풀이 (1) 각 숫자별(0~35) 자릿수에 의한 값을 저장해놓는 배열을 만든다. ex) AB 3C 수 (i) 0 1 2 3 4 5 6 7 8 9 10 A B c ... Z 자릿수 값(v[i]) 0 0 0 36 0 0 0 0 0 0 0 36 1 1 0 0 (2) 35로 바꿨을 때 가장 차이가 큰 수부터 차례대로 35로 바꾼다. 즉 수가 i이고, 그 수의 자릿수 값이 v[i]일때, (35-i)*v[i] 가 큰 순서대로 값을 바꾼다. * 그냥 v[i]가 작은것 부터 해서 틀렸음! 2. 소스코드 N=int(input()) L=[] for i in range(N): L.append(input()) K=int(input()) digit=[[i,0] for i in range(36)] def toThree(nu..

1. 풀이 에라토스테네스의 체를 풀 때 처럼 처음에 검사할 숫자만큼 배열을 만들고 제곱 ㅇㅇ수를 삭제하는 식으로 문제를 해결하면된다. 이때 수의 크기 자체는 크고(1,000,000,000,000), min과 max사이의 차이(1,000,000)는 작기때문에 검사를 1부터 하는게 아니라 min부터 한다. ex) min=1001, max=5015 일때 isNoNo=[1,1,1,1....1] (길이는 5015-1001+1) 배열을 만든다. (1) 이후 가장 작은 제곱수인 4(=2^2)부터 차례대로 탐색. 이때 1부터가 아닌 min에 가장 가까운수부터 탐색. (=1004) 제곱수 제곱 ㅇㅇ수 4 1004 1008 1012 1016 1020 1024 1028 ... 5012 (2) 그 다음 가장 작은 제곱수 9(..

https://programmers.co.kr/learn/courses/30/lessons/12923 코딩테스트 연습 - 숫자 블록 1 10 [0, 1, 1, 2, 1, 3, 1, 4, 3, 5] programmers.co.kr 1. 풀이 위와 같은 규칙으로 블록을 설치하여 1번블록부터 10,000,000번 블록까지 규칙을 모두 적용하면 최종블록은 아래와 같다. i 1 2 3 4 5 6 7 8 9 10 11 ... d[i] 0 1 1 2 1 3 1 4 3 5 1 ... 이 블럭의 규칙은 바로 [ d[i]는 i의 약수중 자기자신을 제외한 가장 큰 숫자 ] 라는 것이다. 따라서 d[i]=i/(i의 약수 중 1을 제외한 가장 작은 숫자) 가 된다. 이때 주의할점은 (1) i가 소수(약수가 1or 자기자신)밖에..

1. 풀이 (1) 1만으로 구성된 두 숫자 a,b의 최대공약수 c도 1만으로 구성됨. (2) 이때 a의 1의개수,b의 1의개수의 최대공약수 = c의 1의개수 (3) 속도관련(곱하기로표현, 포문쓰기, int로 출력) - 곱하기로표현(소스코드1) 포문쓰기(소스코드2) 포문+int로 출력(소스코드3) pypy 통과 시간초과 시간초과 python 통과 통과 시간초과 - 곱하기로 표현 (소스코드1) print("1"*N) -포문쓰기 (소스코드2) ans="" for i in range(N): ans+="1" print(ans) - int로 출력 (소스코드3) ans="" for i in range(N): ans+="1" print(int(ans)) 2. 소스코드 (1) 소스코드1 a,b=map(int,input(..

1. 풀이 (1) 전체 문자열을 N번반복 (2) 전체 문자열의 i번째 반복때(i번째 숫자일때) 아래와 같은경우가 나올때까지 스택에서 숫자를 뽑음 ① 스택에 숫자가 없는경우 ② 스택에서 뽑은 숫자가 i번째 숫자보다 크거나 같을때 ③ 지울수 있는 횟수를 다 썼을때 (3) 최종적으로 나온 stack에서 왼쪽부터 N-K개까지의 숫자가 답이됨. ​ 2. 소스코드 from collections import deque N,K=map(int,input().split()) num=input() size=len(num) cut=0 stack=deque([num[0]]) isFull=False for i in range(1,size): intI=int(num[i]) # 1. 스택에 숫자가 없으면 그만 while(stack)..

1. 풀이 8을 쓸 수 밖에 없는 상황은 "앞자리에서 부터 검사했을 때 두숫자의 같은 위치(자릿수)에 8이 있는 경우"뿐이다. 같은 자릿수에 다른 숫자가 나오면(당연히 R이 크다) 해당 위치부터 끝까지는 무조건 8이아닌 다른 숫자로 채울 수 있다. 따라서 반복종료. ​ 2. 소스코드 L,R=input().split() size=len(R) L=L.zfill(size) ans=0 for i in range(size): if L[i]==R[i]: if L[i]=="8": ans+=1 else: break print(ans)

1. 풀이 난이도에 매몰되지 말것. 실버1이지만 정말 생각하기 어렵다. 쉬운 문제라고 얕보지말고, 어려운 문제라고 겁내지말자 ​ 풀어야 할것은 2가지. ㉠가장 마지막에 떨어지는 개미의 시간 ㉡가장 마지막에 떨어지는 개미. ​ 개미의 속도가 같고, 만나는 즉시 반대방향으로 간다. 이를 통해 알 수 있는 것 3가지가 있다. (1) 첫번째, 개미번호만 바뀐 채 같은 개미가 갈길을 그대로 간다고 생각해도 무방하다. ex) (좌표) - - 3 - (-5) - - - - (개미번호) (1) (2) 즉 위와같은 상황에서 (1)개미는 오른쪽으로 가다가 4에서 (2)개미를 만나고, 개미번호만 (2)로 바뀐채 10에서 떨어지고, (2)개미는 왼쪽으로 가다가 4에서 (1)개미를 만나고, 개미번호만 (1)로 바뀐채, 0에서 ..

1. 풀이 (1) 각 숫자의 계수를 구해준 후 (2) 계수가 가장 큰 숫자부터 9에서 0까지 차례대로 넣어준다. 이때 알파벳이 10개이상일 때(숫자 0까지 써야할 때) 첫째자리에 있는 숫자가 0이되지 않도록 주의한다. ​ ex) (1) 숫자의 계수 구하기 ABC : 100A+10B+C BCA : 100B+10C+A 총합 => 101A+110B+11C ​ (2)계수가 가장 큰 수부터 9에서 0까지 차례대로 넣기. 정렬하면 => 110B,101A,11C 계수가 큰 수 부터 9씩 넣기 (B=9, A=8, C=7) ​ ※참고 : [boj]1339 단어수학 ​ 2. 소스코드 N=int(input()) gasoo=[[0,"A"],[0,"B"],[0,"C"],[0,"D"],[0,"E"], [0,"F"],[0,"G"]..

1. 풀이 (1) 물병의 개수가 a일때, 최대로 합칠 수 있는 개수를 반환하는 함수 cheak(a)를 만든다. - 2로 나누었을 때 몫이 묶인 물병의 수가되고, 나머지가 묶이지 않은 물병의 수가된다. ​ (2) i는 N에서 시작하여 1씩 증가하면서 cheak(i)가 K이하가 되는 첫번째 수를 구한다. - 그 수가 최소로 더 필요한(더 사야할) 물병의 수가 된다. ​ 2. 소스코드 N,K=map(int,input().split()) def cheak(num): ans=0 while(1): a=num//2 b=num%2 ans+=b num=a if num==0: break return ans if K>=N: print(0) else: i = N while(1): if cheak(i)

1. 풀이 가장 큰 줄어드는 숫자는 9876543210 이므로 0부터 포문을 돌리면 당연히 시간초과. 재귀적인 방법이나 수학적인 구현으로 문제를 해결하려고 했으나 방법이 떠오르지 않았다. ​ 결론은 조합을 이용하여 모든 경우를 다 구하고 N번째를 출력하면 된다. 만들 수 있는 모든 줄어드는 수는 10C1+10C2+10C3...10C10개 이다. (하나의 경우의 수를 뽑은 후 내림차순으로 정렬 시켰을때 특정한 하나의 줄어드는 숫자에 대응 된다.) 즉 경우의 수를 다 합쳐도 1024밖에 되지 않기 때문에 위의 방법으로 풀 수가 있다. ​ *나올 수 있는 경우의 수를 구할 수 있고, 시간복잡도를 계산 후 완전탐색이 가능한, 위와 같은 경우를 유의하자. ​ 2. 소스코드 from itertools import ..

1. 풀이 처음엔 에라토스테네스의 체를 이용하여 소수를 모두 구하고, dfs를 이용하여 구하려고 했다. (소스코드1) (1)소수리스트가 정렬되어 있기 때문에 크기가 N보다 커지면 벡트래킹. (2) i번째 숫자를 추가했을때 x값이 나오는 경우는 더이상 탐색하지 않기위해서 visited[i][x]를 관리해 주었지만 시간초과가 났다. ​ 정답은 골드바흐의 추측을 응용해서 풀이하는것이였다. (소스코드2) [골드바흐의 추측] 2보다 큰 모든 짝수는 2개의 소수의 합으로 표현할 수 있다. 이를 응용하면 가장 작은 네개의 소수로 만들 수 있는 수 8(2+2+2+2)이상의 숫자는 소수4개로 표현할 수 있다는 뜻인데 그 방법은 다음과 같다. ​ (1) N이 짝수일때 N이 짝수일때는 N-4도 짝수이다. (N-4>=4) 따..

1. 풀이 처음엔 dfs로 완전탐색했고 시간초과가 발생했다. (소스코드1) 규칙을 찾아서 풀어야 한다. 처음에 같은모양을 갖고 있지 않는 행은 열 단위로 스위치를 누를 때 절대 같아질 수 없다. 즉 (1) 동시에 켜져있는 행이 될 수 있는 행들 시작할 때 같은 모양을 갖는 행들 (union find로 찾았다) (2) 해당 집합이(같은 모양을 갖는 행들) k번째에 켜져있는상태가 될 수 있는가? 시작할때 0의 개수와 k를 2로 나눈 나머지가 같다 ​ 2. 소스코드1 (시간초과,dfs 완전탐색) N,M=map(int,input().split()) L=[] for i in range(N): L.append(list(input())) k=int(input()) def push(j): for i in range(N..

1. 풀이 (1) 가장 큰 숫자를 만들기 위해선 최대한 많은 자릿수를 확보해야한다. => 최대한 많은 숫자를 사기 위해서 가장 싼 숫자를 구매한다 (pick=[a,b,c,d] => d*1000+c*100+b*10+a를 나타낸다) (2) 가장 큰 자릿수 부터 큰 숫자로 바꿀 수 있는지 (남은돈)과 (바꿀때 드는 차액)을 비교한다. => pick에 가장 오른쪽 원소부터 가장 큰 숫자에서 하나씩 작은 숫자로 내려오며 확인한다. ​ *예외 (1) 0이 가장 싼 경우가 있다. 이경우 시작숫자가 0000...이된다(pick=[0,0,0,0...]) 이때 0을 산다고 돈을 다 쓰고 다른 숫자를 살 수 없으면, 숫자를 만들 수가 없다. 따라서 그 경우(0만있고 다른숫자를 살 수 없는)를 대비해 0을 다시 환불하고 돈을..