N = int(input())
def makePrimeNumber(num,idx):
if idx == N:
result.append(num)
else:
for last_num in range(1,10,2):
new_num = num*10 + last_num
if isPrime(new_num):
makePrimeNumber(new_num,idx+1)
def isPrime(num):
if num in prime_numbers:
return True
for i in range(2,int(num**0.5)+1):
if num%i == 0:
return False
prime_numbers.add(num)
return True
prime_numbers = set([2,3,5,7])
result = []
for num in [2,3,5,7]:
makePrimeNumber(num,1)
result.sort()
for row in result:
print(row)
이 문제는 처음에 모든 N자리의 숫자를 primnumber 인지를 구했더니 메모리초과가 났던 문제이다.
이 문제를 푸는 방법은 다음과 같다.
이 문제를 보면 우리는 제일 왼쪽부터 한자리숫자씩 늘리면서 모든 경우에 소수인 것을 구하는 것이다.
그러면 우리가 한자리숫자에서 소수인 것은 2,3,5,7 임을 알 수 있다.
그러면 제일 왼쪽은 무조건 2,3,5,7로 시작되게 해준다.
그리고 N자리를 dfs로 구해주면 된다.
현재 num에 10을 곱하고 끝자리를 바꿔가면서 그 값이 소수인지 판별해주면 된다.
그리고 우리는 한자리숫자를 제외한 두자리숫자부터는 끝 숫자부분이 홀수여야지만 소수가 될 가능성임을 알 수 있다.
그러므로 끝자리는 홀수들만 들어가게 해준다.
소수를 판별하는 방법은 이 수의 제곱근까지의 숫자까지 나눠가면서 나눠지는 경우가 있는지 확인해주면 된다.
def checkWin(play):
play_num = players[play]
for x in range(3):
if arr[x][0] == arr[x][1] == arr[x][2] == play_num:
return 2
for y in range(3):
if arr[0][y] == arr[1][y] == arr[2][y] == play_num:
return 2
if arr[0][0] == arr[1][1] == arr[2][2] == play_num:
return 2
if arr[0][2] == arr[1][1] == arr[2][0] == play_num:
return 2
return 0
def dfs(rc,play):
global result
if checkWin((play+1)%2)>1:
return -1
if rc <remain_cnt:
check_result = 10
for idx in range(remain_cnt):
if not visited[idx]:
visited[idx] = True
x,y = remain_list[idx]
arr[x][y] = players[play]
check_result = min(check_result,dfs(rc+1,(play+1)%2))
visited[idx] = False
arr[x][y] = 0
if check_result == 10 or check_result == 0:
return 0
else:
return -check_result
return 0
arr = []
# 1 = X
# 2 = O
# 착수하는 사람 부터
cnt_1 = 0
cnt_2 = 0
remain_cnt = 0
remain_list = []
players = [1,2]
for x in range(3):
temp = list(map(int,input().split()))
for y in range(3):
if temp[y] == 1:
cnt_1 += 1
elif temp[y] == 2:
cnt_2 += 1
else:
remain_cnt += 1
remain_list.append((x,y))
arr.append(temp)
visited = [False for _ in range(remain_cnt)]
start = 0
if cnt_1 > cnt_2:
start = 1
result = dfs(0,start)
answer = ['D','W','L']
print(answer[result])
이 문제는 어려웠던 문제였다. 이 문제는 각각 최선의 수로 둔다는 것은 해당 수를 두고 다음턴에, 지지 않기를 바라는 상황이다.
그래서 상대턴이 시작할때, 이전턴에 뒀던 플레이어의 승리여부를 체크하고 체크를 한뒤에는 음수를 보내준다.
왜냐하면 서로 승패는 반대로 되기 때문이다. 그리고 승부가 나지 않았을 시에는 0을 반환하도록 한다.
def check():
for x in range(3):
prev_num = arr[x][0]
if not prev_num:continue
for y in range(1,3):
if prev_num != arr[x][y]:
break
else:
return prev_num
for y in range(3):
prev_num = arr[0][y]
if not prev_num: continue
for x in range(1,3):
if prev_num != arr[x][y]:
break
else:
return prev_num
prev_num = arr[0][0]
if prev_num:
for k in range(1,3):
if prev_num != arr[k][k]:
break
else:
return prev_num
prev_num = arr[0][2]
if prev_num:
for k in range(1,3):
if prev_num != arr[k][2-k]:
break
else:
return prev_num
return 0
def dfs(rc,player):
check_num = check()
if check_num != 0:
return check_num
if rc == 0: return -1
response = []
for x in range(3):
for y in range(3):
if arr[x][y]:continue
arr[x][y] = player
response.append(dfs(rc-1,3-player))
arr[x][y] = 0
if player in response:return player
if -1 not in response: return (3-player)
return -1
arr = [list(map(int,input().split())) for _ in range(3)]
cnt_1 = 0
cnt_2 = 0
player = 1
r_cnt = 0
for x in range(3):
for y in range(3):
if arr[x][y] == 1:
cnt_1 += 1
elif arr[x][y] == 2:
cnt_2 += 1
else:
r_cnt += 1
if cnt_1 > cnt_2:
player = 2
result = dfs(r_cnt,player)
if result == -1:
print('D')
elif result == player:
print('W')
else:
print('L')
이 풀이가 좀 더 직관적일 수 있다.
모든 결과들을 저장한뒤에 해당 결과 내에서, 해당 플레이어의 번호가 있으면 승리한 것이므로, 해당 플레이어 번호를 보내주고,
무승부인 -1이 없으면 상대방이 이긴거기 때문에 상대방의 플레이어 번호를 return 해준다.
import sys
def input():
return sys.stdin.readline().rstrip()
def check_pick(pick_list,point):
x,y = point
for nx,ny in pick_list:
if abs(nx-x) == abs(ny-y):
return False
return True
def dfs(problem_list,start,pick_list,color):
global result
if len(problem_list) == start:
result[color] = max(result[color],len(pick_list))
return
else:
for idx in range(start,len(problem_list)):
x,y = problem_list[idx]
if check_pick(pick_list,(x,y)):
dfs(problem_list,idx+1,pick_list+[(x,y)],color)
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
result = 0
black_set = []
white_set = []
for x in range(N):
for y in range(N):
if arr[x][y]:
if (x+y)%2:
white_set.append((x,y))
else:
black_set.append((x,y))
result = [0,0]
dfs(black_set,0,[],0)
dfs(white_set,0,[],1)
print(sum(result))
문제를 푼 아이디어는 다음과 같다. 체스판은 흰색판과 검은색판으로 나뉘어져있다. 그리고 비숍이 잡아 먹을수 있는 위치는 같은 색깔에 있는 위치의 비숍일 뿐이다. 그러므로, 흰색과 검은색으로, 좌표를 나눠서, 각각 놓을 수 있는 최대 위치를 찾아주면 된다.
# chw0501님 코드 복기
import sys
def input():
return sys.stdin.readline()
def dfs(left_slash_num):
if visited[left_slash_num]:
return 0
visited[left_slash_num] = True
for right_slash_num in slash_dict[left_slash_num]:
if right_slash[right_slash_num] == -1 or dfs(right_slash[right_slash_num]):
left_slash[left_slash_num] = right_slash_num
right_slash[right_slash_num] = left_slash_num
return 1
return 0
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
right_slash = [-1 for _ in range(2*N+1)]
left_slash = [-1 for _ in range(2*N+1)]
slash_dict = [[] for _ in range(2*N+1)]
for x in range(N):
for y in range(N):
if arr[x][y]:
slash_dict[x+y].append(x-y+N)
result = 0
for left_slash_num in range(2*N):
visited = [False for _ in range(2*N)]
if dfs(left_slash_num):
result += 1
print(result)
더 빨리 풀 수 있는 코드는 대각선으로 나눠서 하는 방법인데 거기서 깔끔한 코드였던 chw0501님의 코드를 복기한 코드이다.
이 문제를 푸는방법은 다음과 같다. 한 위치에 비숍이 위치하면, 이 비숍의 X자 대각선으로는 다른 비숍들을 둘수 없다.
그렇다면, 흰색, 검은색으로만 나누지 말고, 대각선 위치를 기준으로 나눠 보는건 어떨까 라는 아이디어에서 출발된 것이다.
대각선을 (2*N-1)개씩 두 종류로 나뉠수 있다.
먼저 right_slash라고 부를, 오른쪽 아래로 향하는 대각선 모양은 다음과 같이 총 2*N-1개가 있다.
그러면 같은 대각선에 있는지 확인하는 방법은 행을 X 열을 Y로 했을때 (X-Y+N)으로 표현할 수 있다.
그리고 이렇게 좌측 아래로 향하는 슬래쉬를 left_slash라고 하겠다 이것도 위와 동일하게 2*N-1개가 생성되면
같은 집단인지 판별하는 방법은 (X+Y)이다.
그러면 우리는 해당 칸이 놓을수 있는 자리이면, left_slash를 구하고, 그 left_slash내에 해당 좌표의 right_slash 정보를 같이 집어넣어준다.
즉 slash_dict의 key 값은 left_slash의 좌표값이 되고, right_slash가 value가 되도록 넣어주면 된다.
이렇게 사전작업을 해놓은 상태에서 우리는 2개의 slash_list를 만들어놓는다.
각각 left_slash 와 right_slash로
해당의 index는 slash의 몇번째 위치에 있는지를 나타내며, 그 안의 value 값은 서로 반대편의 슬래쉬의 위치를 표시를 해주는 용도이다.
즉 left_slash의 3번째 위치에 5라는 값이 있으면,
3번째 left_slash에 있는 어떠한 점 중 하나를 골랐고, 그 점은 right_slash를 5를가지고 있다.를 의미한다.
즉 특정한 점을 만들 수 있는 것이다.
그러면 우리는 left_slah의 좌측아래로 향하는 슬래쉬를 기준으로 dfs를 진행을 해주면 된다.
def dfs(left_slash_num):
if visited[left_slash_num]:
return 0
visited[left_slash_num] = True
for right_slash_num in slash_dict[left_slash_num]:
if right_slash[right_slash_num] == -1 or dfs(right_slash[right_slash_num]):
left_slash[left_slash_num] = right_slash_num
right_slash[right_slash_num] = left_slash_num
return 1
return 0
이 dfs가 중요한데 이 dfs에서는 기본적으로 다음과 같다.
우리가 입력받은 left_slash_num에 저장된 right_slash_num들을 하나씩 가져온다.
right_slash라는 list에서 초기값으로 있으면 그 자리에 비숍을 놓을 수 있는 것이니,
left_slash에는 right_slash_num을 저장해주고, right_slash에는 left_slash_num을 저장을 해준다.
그러나 만약 해당 right_slash에 특정한 left_slash_num이 저장이 되어있다면,
우리는 위치를 조정해서 다시 놓을 수 있는지 확인을 해주는 것이다.
우리가 A_right라는 right_slash를 찾아볼려고 했더니 right_slash[A_right]의 값이 -1이 아니였고, B_left라는 값이 있었으면,
우리는 DFS를 통해 B_left를 다시 들어가서 B_left안에 있는 다른 right_slash들을 검사를 해서 놓을 수 있는지 확인을 해주는 것이다.
B_left 안에 [A_right,B_right,C_right] 등이 있다고하면,
이 중에 아직 right_slash가 -1인 값이 있으면, 우리는 그 위치를 조정해서 다시 비숍을 놓을 수 있을것이다.
그러나 이러한 경우가 하나도 없다면 비숍을 놓을 수 없기 때문에 0을 반환을 해주고,
한번 방문했던 곳을 다시 방문을 했다는 것은 사이클이 발생하고, 더 비숍을 놓을 곳이 없는것을 의미하기 때문에 0을 반환을 해주면된다.
위와 같은 dfs를 실행을 하면서 1을 반환이 되면, result의 값을 1씩 늘려주고,
최종적으로 result를 출력을 해주면 된다.
말로서 설명하기에는 어렵지만 디버깅도구를 통해 따라가보면 금방 이해할 수 있었다.
두번째 풀이는 이해하기 어려웠지만, 다른 사람의 코드를 보고 이런 방식으로도 할 수 있는걸 알았다.
좀 더 효율적인 방법이 있다는 걸 알고, 다음번에는 이런 코드를 짤 수 있도록 노력해야겠다.
def dfs(cnt,goal,res):
if cnt == goal:
print(*res)
return
else:
for i in range(N):
if visited[i]:
temp = res + [arr[i]]
if tuple(temp) not in record:
visited[i] = False
record.add(tuple(temp))
dfs(cnt+1,goal,temp)
visited[i] = True
N,M = map(int,input().split())
visited = [True]*N
record = set()
arr = list(map(int,input().split()))
arr.sort()
dfs(0,M,[])
import sys
from itertools import product
def input():
return sys.stdin.readline().rstrip()
def dfs(first_num,idx,total):
global result
if idx == line_cnt[1]:
str_total = str(total)
str_set = set(str_total)
if len(str_total) == line_cnt[idx+2] and not (str_set-total_num):
result += 1
else:
for k in int_total_num:
temp = k*first_num
str_temp = str(temp)
str_set = set(str_temp)
if len(str_temp) == line_cnt[idx+2] and not (str_set-total_num):
number_of_digit = 10**idx
temp_num = temp * number_of_digit
dfs(first_num,idx+1,total+temp_num)
N = int(input())
list_ = input().split()
K = input()
list__ = input().split()
if len(K) == 0:
K = int(list_[N])
list__ = list_[N + 1 : ]
list_ = list_[ : N]
else:
K = int(K)
line_cnt = list(map(int,list_))
number_list = list__[:]
total_num = set(number_list)
int_total_num = set(map(int,number_list))
result = 0
for num_line1 in product(number_list,repeat=line_cnt[0]):
first_line_num = int(''.join(num_line1))
dfs(first_line_num,0,0)
print(result)
이 문제의 아이디어 자체는 그리 어렵지 않다.
모든 것을 다 구해보면 된다.
하다가, 안되는 경우가 발생하면 되돌아가서 새로운 걸 하면 된다.
저같은 경우엔 첫줄의 숫자는 product를 이용해 구했다.
그리고 두번째 숫자부터는 직접 중복순열을 해주면서, 중간에 모든 조건을 만족해야지만, 그 다음 조건으로 갈 수 있게 해주었다.
그리고 주어진 숫자가 있는지 없는지는 차집합을 통해 길이가 0이면 전부 있는것이므로, 길이가 0인경우에만 통과시켜줬다.
import sys
def input():
return sys.stdin.readline().rstrip()
def choose_1(idx,val):
global K
if idx == line_cnt[0]:
choose_2(0,0,val)
return
else:
for i in range(K):
choose_1(idx+1,val*10+number_list[i])
def check_length(val):
val = str(val)
return len(val)
def check_number(val):
while val:
if not number_visit[val%10]:
return False
val = val//10
return True
def choose_2(idx,val,first_num):
global K,result
if idx == line_cnt[1]:
last_num = first_num * val
if check_length(last_num) == line_cnt[-1] and check_number(last_num):
result += 1
return
else:
for i in range(K):
if check_length(first_num*number_list[i]) == line_cnt[idx+2] and check_number(first_num*number_list[i]):
choose_2(idx+1,val*10+number_list[i],first_num)
N = int(input())
list_ = input().split()
K = input()
list__ = input().split()
if len(K) == 0:
K = int(list_[N])
list__ = list_[N + 1 : ]
list_ = list_[ : N]
else:
K = int(K)
result = 0
line_cnt = list(map(int,list_))
number_list = list(map(int,list__))
number_visit = [False for _ in range(10)]
for num in number_list:
number_visit[num] = True
choose_1(0,0)
print(result)
이 방식은 좀 더 깔끔한 방식인것같다.
여기는 나머지를 이용해서 각 자리수를 구하고, 그때 숫자가 있는지 없는지는 리스트의 방문표시로 해주었다.
from collections import deque
import sys
R,C,T = map(int,input().split())
arr = []
start = []
for x in range(R):
temp = list(input())
for y in range(C):
if temp[y] == 'G':
start = (x,y)
arr.append(temp)
stack = []
stack.append((*start,0,set()))
time = 0
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
while time<T:
new_stack = []
for x,y,eat,visited in stack:
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx<R and 0<=ny<C:
if arr[nx][ny] == 'S' and (nx,ny) not in visited:
new_visited = set()
new_visited.add((nx,ny))
new_visited = new_visited | visited
new_stack.append((nx,ny,eat+1,new_visited))
result = max(eat+1,result)
elif arr[nx][ny] != '#':
new_stack.append((nx,ny,eat,visited))
stack = [row[:] for row in new_stack]
time += 1
print(result)
대회때 풀었던 풀이는 다음과 같다 BFS를 해주면서, 모든 이동경로를 누적해줬다.
그리고 visited에 없는 경우에만 고구마를 먹도록 해줬다.
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
def dfs(node,time,eat):
global T,result,R,C
if time == T:
result = max(result,eat)
return
else:
result = max(result,eat)
for i in range(4):
nx = node[0] + dx[i]
ny = node[1] + dy[i]
if 0<=nx<R and 0<=ny<C and not vistied[nx][ny]:
vistied[nx][ny] = True
if arr[nx][ny] == 'S':
dfs((nx,ny),time+1,eat+1)
else:
dfs((nx,ny),time+1,eat)
vistied[nx][ny] = False
elif 0<=nx<R and 0<=ny<C and vistied[nx][ny] and arr[nx][ny] !='#':
dfs((nx,ny),time+1,eat)
R,C,T = map(int,input().split())
result = 0
vistied = [[False for _ in range(C)] for _ in range(R)]
arr = []
start = []
for x in range(R):
temp = list(input())
for y in range(C):
if temp[y] == '#':
vistied[x][y] = True
elif temp[y] == 'G':
start = (x,y)
arr.append(temp)
dx = [-1,1,0,0]
dy = [0,0,-1,1]
dfs(start,0,0)
print(result)
import sys
sys.setrecursionlimit(10000)
def roll(x,y,vis,cnt,roll_cnt):
global result,total_cnt
if total_cnt == cnt:
result = min(result,roll_cnt)
return
if roll_cnt > result:
return
vis[x][y] = True
dx = [-1,1,0,0]
dy = [0,0,1,-1]
for i in range(4):
move = 1
nx = x + dx[i]*move
ny = y + dy[i]*move
while 0<=nx<N and 0<=ny<M and vis[nx][ny] == False:
nx = nx + dx[i]
ny = ny + dy[i]
move += 1
if move>1:
for m in range(1,move):
nx = x + dx[i]*m
ny = y + dy[i]*m
vis[nx][ny] = True
roll(nx,ny,vis,cnt+(move-1),roll_cnt+1)
for m in range(1,move):
nx = x + dx[i]*m
ny = y + dy[i]*m
vis[nx][ny] = False
tc = 1
while True:
try:
N,M = map(int,input().split())
arr = []
total_cnt = N*M
visited = [[False]*M for _ in range(N)]
for x in range(N):
temp = list(input())
for y in range(M):
if temp[y] == '*':
visited[x][y] = True
total_cnt -= 1
arr.append(temp)
result = float('inf')
for x in range(N):
for y in range(M):
if arr[x][y] == '.':
copy_visited = [row[:] for row in visited]
roll(x,y,copy_visited,1,0)
if result == float('inf'):
result = -1
print(f'Case {tc}: {result}')
tc += 1
except:
break
이 문제는 문제에 주어진 조건대로 굴리면 되는 문제였다.
여기서 주의해야할 점은 최소 이동거리가 1이상이어야하고, 그때에만 움직여주면서 VISITED를 반대 상태로 바꿔줬다가, 탐색이 끝나면 원래 상태로 바꿔주는 것이 필요로 했다.
또한 최소 이동횟수이므로, 이동횟수보다 많은 로직에 대해서는, 탐색을 그만두고 되돌아가는 백트래킹이 필요로 했다.
처음에 최소 이동횟수가 아닌, N*M 보드 완주하는 횟수를 구하는 줄 알고, 잘못 구현하는 실수를 저질렀었다.
