1. 풀이 조건에 맞게 구현하면된다. 설치할때는 설치할 수 있는지 조건을 만족하는지, 삭제할때는 삭제한 후에도 모든 기둥과 보가 존립할 수 있는지를 따지면 된다. 입력이 좌표평면에서 x,y로 주어지는데, 이를 행렬로 바꾸면 x가 r, y가 c, 즉 좌표평면을 시계방향으로 90도 회전했다고 생각하면 된다. 그리고 기둥,보 설치여부를 리스트 L을 통해서 관리했다 (L[r][c][a] : r행 c열의 a가 설치되어있으면 1, 설치안되어있으면 0, 보는 해당좌표의 아래방향, 기둥은 해당좌표의 우측방향) 즉 x행,y열의 0(기둥)을 설치하면 L[x][y][0]=1, 삭제하면 L[x][y][0]=0 x행,y열의 1(보)를 설치하면 L[x][y][1]=1, 삭제하면 L[x][y][1]=0 으로 나타내준다. ​ 설치하..

1.풀이 0으로 모두 초기화 시켜놓고, 검사해야하는 점 마다 time=1일때 부터 time=s 까지 중 언제 색칠됐전 점인지를 확인해준다. (정확히 말하면 time=1이 가장 마지막으로 색칠된 점이고, time=s가 가장 처음 색칠된 점) ​ ex) 예시 i,j가 검은점인지 아래의 순서대로 확인해준다. (색이 칠해졌음이 확인되었으면 바로 다음 점 확인) 1*1검은 점에 속해있는지 time=1일때 3*3검은 점에 속해있는지 time=2일때 5*5검은 점에 속해있는지 time=3일때 ​ 이때 짝수와 홀수일 때 범위가 달라지는것에 주의한다. ​ 2. 소스코드 import sys s,N,K,R1,R2,C1,C2=map(int,input().split()) #시간 0이면 그냥끝 if s==0: print("0")..

1. 풀이 (1) 모든 가능한 궁수의 위치에 대한 경우의 수를 구한다. (2) 하나의 경우의 수에 대해서 아래를 수행한다 - 궁수공격 - 적이동 ​ * "(1) 궁수의 공격"에서 여러 궁수가 조건에만 만족한다면 같은 적을 동시에 쏠 수 있다는것을 주의한다. * 또한 "(1) 궁수의 공격" 은 [1. 극한의 구현]을 하거나 짧은거리부터 공격을 하고, 거리가 같으면 왼쪽부터 공격하므로 [2. bfs를이용]할 수 있다. ​ [1. 극한의 구현] from copy import deepcopy from itertools import combinations N,M,D=map(int,input().split()) L=[] for i in range(N): L.append(list(map(int,input().spli..

* 베이스상태를 list의 요소로( 1루:base[0], 2루:base[1], 3루:base[2] )로 했을때는 시간초과. * 베이스상태를 1루는 a, 2루는 b, 3루는 c 로 바꿔주면 통과 ​ 1. 베이스를 리스트로(시간초과) from itertools import permutations inning=[] n=int(input()) for _ in range(n): inning.append(list(map(int,input().split()))) permu=list(permutations([i for i in range(1,9)],8)) ans=0 #각 경우 확인 for case in permu: nowCase=list(case) nowCase.insert(3,0) nowCase=tuple(nowCa..

1. 풀이 (1) i+j+k=x를 i+j=x-k로 바꿔서 생각한다. (i번째수 + j번째수 = x번째수 - k번째수) (2) x가 가능한지 확인: k가 0번째부터 x-1번째까지 한번돌면서 (x번째-k번째)가 가능(방문되었는지)한지 확인 (3) x까지 추가되서 만들수 있는 숫자 최신화 : j가 0번째부터 x번째까지 돌면서 새로운숫자 (x번째+j번째)를 방문 * Ai의 범위는 -100000~100000이므로 x-k의 범위는 -200000~200000. 따라서 이를 리스트 인덱스로 만들어주려면 0~400000아 되므로 isPossible 리스트는 400001로 초기화 (4) (2),(3)의 과정을 N번반복. O(N^2) ​ 2. 소스코드 N=int(input()) L=list(map(int,input().sp..

1. 풀이 행렬에서 한 점을 축으로 하고, 90도로 회전할 때, 이를 식으로 나타낼 수 있다. 축으로 하는 점을 (x,y), 90도로 회전시킬 점을 (a,b), 회전된 점을 (A,B)라고 할 때 (1) 시계방향으로 회전 A=x-y+b B=x+y-a (2) 반시계방향으로 회전​ A=x+y-b B=-x+y+a ​ 2. 소스코드 x,y를 각각 행과 열로 바꿔서 생각하면, 시계방향이 아닌 반시계 방향으로 움직여야 하고, 입력값 d도 (x는 행, y는 열로) 다르게 생각해 주어야 한다. N=int(input()) myMap=[[0 for _ in range(101)] for _ in range(101)] dR=[1,0,-1,0] dC=[0,-1,0,1] for i in range(N): r,c,d,g=map(in..

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