그냥 하라는대로 하면 되는문제인데 인덱스 장난이 심한 문제. 그래서 코딩에서 가장 중요한건 차분히 침착하게 푸는것 이라는것을 다시한번 상기시키는 문제. 침착해 침착해 from copy import deepcopy N=int(input()) P=list(map(int,input().split())) S=list(map(int,input().split())) #카드덱 dq=[i for i in range(N)] #현재 플레이어상태 player=[[] for i in range(3)] for i in range(N): p=i%3 player[p].append(i) ini=deepcopy(player) #목표값 target=[[] for i in range(3)] for i in range(N): target[..

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

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)

1.풀이 [백준]1035 조각움직이기 (https://sosoeasy.tistory.com/39) 와 비슷한 문제이다. (1) 모든 경우의 수를 조합으로 구한다 (2) (1)에서 구한 경우가 임도연파(Y)가 4명이상인지 확인한다. (3) 4명이상이면 bfs를 통해서 연결되어있는지 확인한다. - 소스코드1 : dfs를 이용하여 연결여부 확인 - 소스코드2 : bfs를 이용하여 연결여부 확인 -> 내생각엔 이게 더 쉽다. * 이런류의 문제를 백트래킹으로 생각하면 조건 처리가 힘들어지는 경우가 많다. 완전탐색으로 보이는 문제는 깔끔하게 순열, 조합으로 풀 수 없을까 고민하는 자세가 필요하다. 2. 소스코드 (1) 소스코드1 (dfs를 이용) from itertools import combinations dR=..

1.풀이 (1) 25개의 위치에 n개의 조각을 둘 수 있는 모든 경우의 수를 구한다 (조합을 이용, n은 최대 5이므로 총 횟수는 최대 25C5=53130) (2) (1)에서 구한 모든 경우에 대해 해당경우가 연결되어 있는 상태인지 구한다 (BFS를 이용한다) (3) 연결되어 있다면 원래상태에서 해당경우를 만들 수 있는 최소상태를 구한다. (각 조각에 고유번호를 매기고, 순열을 이용하여 모든 경우를 확인한다.) 2. 소스코드 from itertools import combinations,permutations from collections import deque dR=[0,0,-1,1] dC=[1,-1,0,0] INF=9876543210 def calDist(A,B): return abs(A[0]-B[0..

0 1 2 3 4 5 6 7 8 9 10 11 행렬에서 위와같이 번호(num)를 매기고 싶다면. (행) i=num//col (열) j=num%col ​ ​ ex) 6의 행렬? 1. num으로 행렬값? 6의 행은 col의 개수 4로 나눈 몫 == 1, 열은 col의 개수 4로 나눈 나머지 == 2. 따라서 (1,2) ​ 2 행렬로 num값? num=i*col개수+j