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. 풀이 (1) 숫자를 넣는 방법 숫자를 1부터 차례대로 적절한 위치에 집어넣는다. 숫자를 1부터 집어넣기 때문에 집어넣을 위치 앞에 아직 차지 않은 부분은 무조건 현재넣을 숫자보다 크고, 이미 차있는 숫자는 현재숫자보다 작다. (2) 세그먼트 트리 따라서 숫자가 들어갈 위치를 세그먼트트리를 이용해서 찾는다. 세그먼트트리를 이용해서 구간합을 구해주는데, 이를 이용하여 현재 위치앞에 몇개의 숫자가 있는지를 빠르게 확인해준다. * 처음에 update함수 따로, 위치를 찾는 함수를 따로 구현해서 시간 초과가 떳다(소스코드1). 위치를 찾으면서 바로 수정을 해야 통과한다. 2. 소스코드 (1) 소스코드1 (update함수, 쿼리함수 따로구현, 시간초과) import sys import math def init..

1. 풀이 이 문제에선 "붙어있는 수열에서 최솟값을 찾는 행위" 를 엄청 많이 해야 한다. (= 이를 쿼리라고 한다) 이때 "붙어있는 수열에서 최솟값을 찾는 행위"를 빠르게 하기 위해 세그먼트트리를 사용한다. 이 문제는 너비는 모든 직사각형이 같지만, 높이만 다르기 때문에 연속된 높이들 중 가장 작은 높이가 만들수있는 직사각형의 높이가 된다. 따라서 높이의 최솟값을 세그먼트 트리에 저장한다. 이때 주의할점은 분할 정복을 할 때 최소 높이를 기준으로 좌 우로 계속해서 탐색을 해야 하기 때문에, 최소높이의 인덱스를 알아야 한다는 것이다. 따라서 세그먼트 트리에는 최소높이와 함께 최소 높이의 인덱스도 저장해야 한다. 2. 소스코드 import math import sys sys.setrecursionlimit..

수열이 있을 때 중에서 연속된 특정구간을 주고, 특정구간의 1. 최댓값([백준]2357 최솟값과 최댓값) 2. 최솟값([백준]10868 최솟값) 3. 합([백준]2042 구간합, [백준]1275 커피숍2) 4. 곱([백준]11505 구간곱 구하기) 을 여러번 구하는 문제는 세그먼트트리를 쓰면 된다. 세그먼트 트리를 사용하기 위해선 보통 아래와 같은 3가지 함수가 필요하다. 1. 주어진 수열을 이용하여 처음으로 세그먼트 트리를 만드는 함수 2. 세그먼트트리의 노드하나를 수정하는 함수 3. 세그먼트트리를 이용하여 구간합(or 구간곱 or 최댓값,최솟값)을 구하는 함수. 각 함수코드는 다음과 같다. 1. 세그먼트트리 초기화 함수. def init(node,start,end): if start==end: tre..

1. 풀이 (1) dp[i][j] = i에서 j까지의 문자가 팰린드롬이 가능하면 1, 그렇지 않으면 0. (2) count[i] = i번째 문자까지의 분할의 개수의 최솟값 여기서 count[i]를 구하는법이 이문제의 핵심이다. i를 구하는 법은 다음과 같다. --------------------------------------------------------------------------- count[i] = j가 1부터 i까지 도는데 이때 i) j부터 i까지가 팰린드롬이면 => count[j-1]+1 ii) j부터 i까지 팰린드롬이 아니면 => count[j-1]+i-j+1 -----------------------------------------------------------------------..

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(..

1. 풀이 처음에는 격자를 이용해서 풀려고 했다. (소스코드1) 0.5초 만에 만나는것을 구현하기 힘들어서 최대범위는 +-2000으로 했고, (x,y)를 (r,c)로 바꿔주기위해 r=2*x+2000, c=2*y+2000으로 하여 4000*4000의 격자를 만들어준 후 문제를 풀었다. 하지만 이 방법으로는 메모리 초과가 났다. ​ 따라서 아래와 같이 격자를 쓰지 않는 방법으로 문제를 풀었다. (1) atomD에 현재 원자들의 상태와 상태를 저장한다 (2) 이동시킨다 - 범위 밖이면 삭제한다 (이동할 때 원자가 범위 밖에서 만나는 경우는 없으므로) - 범위 안이면 cheakD에 저장하고, 바뀐 위치를 새롭게 atomD에 저장한다 (이때 cheakD는 dictionary형태로, key값을 (행,열)과 같은 튜..

1. 풀이 (1) 다른단어의 접두사가 되는 단어는 접두사X 리스트에서 제거한다. (제거 후 남는 단어의 집합이 곧 접두사x집합) ex) h,hi,xi, hio, run, hcc, hipo, runn, runc, runni, running ​ (2) 다른단어의 접두사가 되는 단어는 항상 다른단어보다 크기가 작거나 같다. 따라서 문자열의 길이가 짧은 순서대로 정렬을 하고, 자기 위치보다 뒤에있는 단어와만 비교한다. ​ 2. 소스코드 N=int(input()) L=[] for i in range(N): word=input() L.append(word) L.sort(key=len) ans=0 for i in range(N): nowWord=L[i] isHead=False for j in range(i+1,N):..

1. 풀이 visited로 선이 그어진곳을 표시하기엔 범위가 -1,000,000,000 이상 1,000,000,000 이하 이므로 메모리초과. N의 범위가 N(1≤N≤1,000,000) 이므로 무조건 O(N)으로 풀어야된다. 풀이는 아래와 같다. (1) 선을 sort()해준다. 그럼 시작점 순서대로 소팅된다. (2) preA

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..