1. 내코드(통과) import math N,M,K=map(int,input().split()) # 여자가 남음 if N>=2*M: over=N-2*M isOverWo=True # 남자가 남음 elif N=K: print(M) else: K-=over needTeem=math.ceil(K/3) ans=M-needTeem if ans>=0: print(ans) else: print(0) 2. 숏코딩(통과) n, m, k = map(int, input().split()) ans = 0 while n >= 2 and m >= 1 and n + m - 3 >= k: n -= 2 m -= 1 ans += 1 print(ans)

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을 다시 환불하고 돈을..

1.풀이 합이나 평균을 구할때 수학적 사고를 하자! ​ (1) i번째 숫자가 (0~9중)될 수 있는 모든 수를 찾는다. ex) digitLSize=[[1],[0,8],[8,9]] => 100의자리에 1이 올 수 있고, 10의자리는 0,8이 올 수 있고, 1의자리는 8,9가 올 수 있다. ​ (2) 될 수 있는 모든 경우의 수를 찾는다. * dfs로 완전탐색하려 했지만 메모리 초과가 났다(소스코드1) * 각자리에 올 수 있는 숫자를 나올수 있는 횟수만큼 더하면 총 합을 구할 수 있다. (소스코드2) 위의 예시에서 100의 자리 1은 총 2*2번나오므로 100*1*4, 10의자리 0은 총 1*2번나으모르 10*0*2... ​ 2. 소스코드 (1) 소스코드1 (메모리초과) import sys sys.setre..

1. 풀이 (1) 시간복잡도 그냥 풀면 정말 간단한 백트래킹 문제이지만 시간이 O(2^(N*N)) 이므로 초과이다. 해법은 체스판의 특성을 생각하고 하얀색 체스판에 채울 수 있는 최대의 비숍과 검은색 체스판에 채울 수 있는 최대의 비숍을 각각 따로구해서 더해주는 것이다. 이렇게 하면 시간복잡도는 아래와 같이 된다. O(2^(N/2*N/2)+2^(N/2*N/2))=O(2^(N/2*N/2)) (2) N이 짝수일 때 주의사항 N이 홀수이면 확인할 블럭이 아래와 같이 2씩 증가하지만 0 3 5 7 9 N이 짝수이면 확인할 블럭이 마지막 or 마지막 바로앞 열에서 3 or 1씩 증가해야 한다 0 2 5 7 8 10 13 15 따라서 이를 유의해서 탐색을 해줘야한다! 2. 소스코드 dR=[-1,-1,1,1] dC=..

파스칼의 삼각형으로 조합을 구할 수 있다. 위의 삼각형 형태를 행렬로 바꾸면 하삼각행렬로 만들 수 있다. (i,j)위치의 값이 정확히 iCj가 되는 예쁜 형태가 된다. (j==0일때만 1을 넣어주면된다.) ​ ex)[boj]11051_이항계수2 #include #include using namespace std; long long pascal[1000][1000]; int main() { int N, K; int max = 10007; cin >> N >> K; for (int n = 0; n

1.풀이 (1) a의 b승을 구하는문제. 진짜 a를 b번 곱하면 당연히 시간초과. (2) a^b => (a제곱)^(b//2) 로 계산하는것이 핵심. EX) 2^4는 2를 네번곱해야 하지만, 2^4->4^2->16^1로 하면 3번만에 계산가능 (3) 제곱수가 홀수인 경우는 하나빼서 계산해야 하기 때문에 경우의 수를 나눠준다. (4) 제곱수가 1이 될 때 까지 재귀를 반복한다. ​ 2. 소스코드 A, B, C = map(int, input().split()) def power(a,b): #1이면 끝 if b==1: return a%C #짝수이면 제곱 if b%2==0: return power(a**2%C,b//2) #홀수이면 곱하고 제곱 else: return (a*power(a**2%C,b//2))%C d..

1. 풀이 처음엔 N개의 점을 모두 사용하여 N/2개의 선분을 만들었을 때 선분의 합이 최소가 되는 경우를 구해야 한다고 생각했다. 따라서 nC2*n-2C2*n-4C2...*4C2*2C2의 경우를 생각했었다. 하지만 문제에서 요구하는것은 "벡터의합의 길이"이다. ​ 즉 4개의 점 (x1,y1),(x2,y2),(x3,y3),(x4,y4) 가 있을 때 (x_a+x_b -x_c-x_d , y_a+y_b-y_c-y_d )의 길이의 최솟값을 구하면 된다. ​ 따라서 모든점의 개수(N개)중 시작점의 개수(N//2)를 뽑는 경우(나머지는 자동으로 도착점이 된다)는 nCn//2 이므로 해당 경우를 완전탐색하면 답이 된다. ​ 2.소스코드 import sys from itertools import combinations..

0~size-1까지의 모든 숫자들에 대해서 소수인지를 판별 1. isNotPrime는 소수인것이 0 int isNotPrime[size]; void eratosthenes(size) { isNotPrime[1] = 0; isNotPrime[1] = 1; // 0과 1은 소수가 아니다. for (int i = 2; i*i < size; i++) { if (!isNotPrime[i]) { //소수이거나, 아직 탐색을 안했다면 (isNotprime은) 0 for (int j = i * i; j < size; j += i) { isNotPrime[j] = 1; } } } } 2. isPrime는 소수인것이 1 #에라토스테네스 isPrime=[1 for i in range(size)] def prime(): is..