# 1978 소수 찾기

N = int(input())
arr = list(map(int, input().split()))
prime = [i for i in range(2,1001)]

for i in range(2,round(1000**(1/2))):
  for j in range(2,1000//i+1):
    if i*j in prime:
      prime.remove(i*j)
R = 0
for i in arr:
  if i in prime:
    R += 1

print(R)

문제의 범위가 1000까지라 for문을 통해 1000까지의 소수 리스트를 만들고

입력받은 값이 소수 리스트에 있으면 값을 세어 출력하게 코드를 짰다.

2022.01.21

백준 15652 N과 M (4)

# 15652 N과 M (4)

N, M = map(int, input().split())
R = []

def dfs():
    if len(R) == M:
        print(*R)
        return
    
    for i in range(1,N+1):
        try:
            if i >= R[-1]:
                R.append(i)
                dfs()
                R.pop()
        except:
            R.append(i)
            dfs()
            R.pop()

dfs()

예시 출력을 보면 뒤의 숫자가 항상 바로 앞 숫자보다 크거나 같은 것을 알 수 있다.

때문에 R[-1] 보다 크거나 같으면 되는데 그냥 하나만 넣어주면 R = [] 으로 요소가 없어서 range오류가 나온다.

이걸 try; except구문으로 해결해줬다.

2022.01.20

백준 15651N과 M (3)

#15651 N과 M (3)

N, M = map(int, input().split())
R = []

def dfs():
    if len(R) == M:
        print(*R)
        return
        
    for i in range(1,N+1):
        R.append(i)
        dfs()
        R.pop()

dfs()

처음에 return을 넣어주지 않았더니 무한 재귀가 되어버려서 depth오류가 나왔다.

재귀적 방법을 사용할 때는 return으로 어디서 빠져나올지 잘 생각해야겠다.

백트래킹 문제.. 그런데 백트래킹이 뭔지 잘 모르겠다.

dfs와 같이 재귀적으로 진행하고, 사이에 조건을 추가해서 아닌 가지를 잘라내는 것?

또 여러 문제를 풀어봐야지

#15649
import itertools

N, M = map(int, input().split())
arr = [ i for i in range(1,N+1)]

R = list(itertools.permutations(arr,M))

for i in R:
    print(' '.join(map(str,i)))

itertools의 permutations를 사용하면 중복을 제외하고 가능한 순열조합을 모두 만들어준다.

백트래킹으로 풀어보려고 했는데 재귀 조건을 어떻게 주어야 할지 떠오르지 않아서 다르게 풀어봤다. 

2022.01.14

백준 1697 숨바꼭질

# 1697 숨바꼭질
from collections import deque

N, K = map(int,input().split())

# 리스트 인덱스에 점으로 이동하는 시간을 저장하기 위해서 arr생성
# x-1이 더 빠른 경우도 있기 때문에 가장 큰 값에서 +2해준다.
if N >= K:
    arr = [0] * (N+2)
else:
    arr = [0] * (K+2)
    
def bfs(x):
    queue = deque()
    queue.append(x)
    arr[x] = 0
    if x == K:   # N == K 같은 경우 0 리턴
        return 0
    while queue:
        a = queue.popleft()
        dx = [1,-1,a]
        for i in range(3):
            nx = a + dx[i]
            if 0 <= nx < len(arr) and arr[nx] == 0:
                queue.append(nx)
                arr[nx] = arr[a] + 1
bfs(N)
print(arr[K])

x와 K 값이 같을 때 값을 지정해주는 것과 arr의 범위를 잘 못 정해줘서

문제가 무엇일까 하고 한참을 쳐다보았었다.

# 1436 영화감독 숌
N = int(input())
arr = []

d = 665
while len(arr) != N:
    a = list(str(d))
    for i in range(len(a)-2):
        if a[i]+a[i+1]+a[i+2] == '666':
            arr.append(d)
            break
    d += 1
print(arr[N-1])

#1158
from collections import deque

N, K = map(int, input().split())

R = []
queue = deque()
for i in range(1,N+1):
    queue.append(i)
    
while queue:
    for i in range(K-1):
        queue.append(queue.popleft())
    R.append(queue.popleft())
    
print('<', end = '')
print(*R, sep = ', ', end = '')
print('>')

백준 7569 토마토

from collections import deque

m,n,h = map(int, input().split())

graph = []

for _ in range(h):
    graph.append([ list(map(int,input().split())) for _ in range(n) ])

dx = [-1,1,0,0,0,0]
dy = [0,0,-1,1,0,0]
dz = [0,0,0,0,-1,1]

queue = deque()

def bfs():
    for i in range(h):
        for j in range(n):
            for k in range(m):
                if graph[i][j][k] == 1:
                    queue.append((i,j,k))
    
    while queue:
        x,y,z = queue.popleft()
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]

            if 0 <= nx < h and 0 <= ny < n and 0 <= nz < m :
                if graph[nx][ny][nz] == 0 :
                    queue.append((nx,ny,nz))
                    graph[nx][ny][nz] = graph[x][y][z] + 1

bfs()
R = []
for i in range(h):
    for j in range(n):
        if 0 in graph[i][j]:
            R.append(0)
        else:
            R.append(max(graph[i][j]))
if 0 in R:
    print(-1)
else:
    print(max(R)-1)

처음에 2차원 배열로 풀려다가 상자 층이 넘어가는 것을

인접면으로 탐색하는 걸 해결 못해서 포기했다.

결국 3차원으로 풀었는데 어제 풀었던 7576번 문제와 똑같고

차원이 하나 추가돼서 좌표설정만 헷갈리지 않으면 됐다.

#1181
N = int(input())
arr = [input() for i in range(N)]

H = list(set(arr)) # 중복 제거
H.sort()
H.sort(key = len)  # 길이값으로 또 정렬
for i in H:
    print(i)

#1085
x, y, w, h = map(int, input().split())
print(min(x,y,w-x,h-y))