23.08.30

7-1. 최대 점수 구하기

time, score로 따로 나눠서 구할 생각을 못하고 한번에 튜플로 저장해서 처리할생각을 하니까 구현도, 문제푸는 방식도 한정적이게 됨.

• 에러

def DFS(L, saveScore, saveTime):
    if L==n-1: #에러
        if saveTime==m:
            return saveScore
    else:
        for i in range(n):
            DFS(L+1, saveScore+score[i], saveTime+time[i])
            DFS(L+1, saveScore, saveTime)

n, m = map(int, input().split())
score = []
time = []
for _ in range(n):
    a, b = map(int, input().split())
    score.append(a)
    time.append(b)
print(DFS(0,0,0))

• 정답

"""
1. 종료조건 잘못함
2. 비교하기 위한 부분을 생각 못함 
"""

def DFS(L, saveScore, saveTime):
    global res
    if saveTime>m:
        return
    if L==n:
        if saveScore>res:
            res=saveScore
    else:
        for i in range(n):
            DFS(L+1, saveScore+score[L], saveTime+time[L])
            DFS(L+1, saveScore, saveTime)

n, m = map(int, input().split())
score = []
time = []
for _ in range(n):
    a, b = map(int, input().split())
    score.append(a)
    time.append(b)
res = -1e9
DFS(0, 0, 0)
print(res)

7-2. 휴가

이코테 dp문제였는데 풀지 못했다는 점이 심각쓰
BFS를 여전히 다루지 못한다는 점

def DFS(L, sum):
    global res
    if L==n+1:
        if sum>res:
            res=sum
    else:
        if L+t[L]<=n+1: #상담기간 제한
            DFS(L+t[L], sum+p[L]) #(현재날짜+다음상담기간, 금액 누적)
        DFS(L+1, sum) 

n = int(input())
t = []
p = []
for i in range(n):
    a, b= map(int, input().split())
    t.append(a)
    p.append(b)

res = -1e9
t.insert(0,0) #인덱스를 날짜로 하기 위해서 0 넣기
p.insert(0,0)

7-3. 양팔저울

왼, 오, 적용하지 않을경우 3가지로 나눠서 DFS구현

def DFS(L, sum):
    global res
    if L==n:
        if 0<sum<=s: #sum이 양수일경우 ~ 총 무게까지 // 대칭구조임으로 음수는 제외하면 된다 
            res.add(sum)
    else:
        DFS(L+1, sum+g[L]) #왼쪽
        DFS(L+2, sum-g[L]) #오른쪽
        DFS(L+1, sum) #사용하지 않을 경우

n = int(input())
g= list(map(int, input().split()))
s = sum(g)
res = set() # 중복제거
DFS(0,0)
print(s-len(res))

7-4. 동전 바꿔주기

"""
20
3
5 3
10 2
1 5
"""
def DFS(L, sum):
    global cnt
    if sum>t:
        return
    if L==k:
        if sum==t:
            cnt+=1
    else:
        for i in range(cn[L]+1):
            DFS(L+1, sum+(cv[L]*i))

t = int(input())
k = int(input())
cv = []
cn = []
for i in range(k):
    a, b = map(int, input().split())
    cv.append(a)
    cn.append(b)
cnt = 0
DFS(0,0)
print(cnt)

7-5. 동전 분배하기

사람을 기준을 DFS에 넣어서 분배 백트랙킹을 이용했는데 혼자서 구현 X

"""
동전 분배 하기
7
8
9
11
12
23
15
17

coin = [8,9,11,12,23,15,17]
"""

def DFS(L):
    global res
    if L==n:
        cha=max(money)-min(money)
        if cha<res:
            tmp=set()
            for x in money:
                tmp.add(x)
            if len(tmp)==3:
                res=cha
    else:
        for i in range(3):
            money[i]+=coin[L]
            DFS(L+1)
            money[i]-=coin[L]


n = int(input())
money = [0]*3
res = 1e9
coin = [int(input()) for _ in range(n)]
DFS(0)
print(res)

7-6. 알파코드

"""
알파코드
# 한 글자씩 쪼개기
# 26 이하 까지 두 자릿 수로 쪼개기
"""

def DFS(L,P):
    global cnt
    if L==n:
        cnt+=1
        for j in range(P):
            print(chr(res[j]+64), end='')
        print()
    else:
        for i in range(1,27):
            if code[L]==i:
                res[P]=i
                DFS(L+1, P+1)
            elif i>=10 and code[L]==i//10 and code[L+1]==i%10:
                res[P]=i
                DFS(L+2, P+1)

code=list(map(int, input()))
n = len(code) #종착점
code.insert(n, -1) #에러
res=[0]*(n+3)
cnt=0
DFS(0,0)
print(cnt)

7-7. 송아지 찾기

from collections import deque
MAX=100000
s, e = map(int, input().split())
ch=[0]*(MAX+1)
dis=[0]*(MAX+1)
ch[s]=1
dis[s]=0
dQ = deque()
dQ.append(s)

while dQ:
    now = dQ.popleft()
    if now == e:
        break
    for x in (now-1, now+1, now+5):
        if 0<x<=MAX:
            if ch[x]==0:
                dQ.append(x)
                ch[x]=1
                dis[x]=dis[now]+1
print(dis[e])

7-8. 사과나무

from collections import deque
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ch=[[0]*n for _ in range(n)]
sum=0
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
Q = deque()
Q.append((n//2,n//2))
ch[n//2][n//2]=1
sum+=a[n//2][n//2]
L=0

while True:
    if L==n//2:
        break
    h = len(Q)
    for i in range(h):
        tmp= Q.popleft()
        for j in range(4):
            x=tmp[0]+dx[j]
            y=tmp[1]+dy[j]
            if ch[x][y]==0:
                sum+=a[x][y]
                ch[x][y]=1
                Q.append((x,y))
    L+=1
print(sum)

7-9. 미로의 최단거리

• 정답

"""
미로의 최단거리
0 0 0 0 0 0 0 
0 1 1 1 1 1 0 
0 0 0 1 0 0 0 
1 1 0 1 0 1 1 
1 1 0 1 0 0 0 
1 0 0 0 1 0 0 
1 0 1 0 0 0 0

"""
from collections import deque
dx = [-1,0,1,0]
dy= [0,1,0,-1]
board= [list(map(int, input().split())) for _ in range(7)]
dis = [[0]*7 for _ in range(7)]
Q = deque()
Q.append((0,0))
board[0][0]=1

while Q:
    tmp = Q.popleft()
    for i in range(4):
        x=tmp[0]+dx[i]
        y=tmp[1]+dy[i]
        if 0<=x<=6 and 0<=y<=6 and board[x][y]==0:
            board[x][y]=1
            dis[x][y]=dis[tmp[0]][tmp[1]]+1
            Q.append((x,y))
if dis[6][6]==0:
    print(-1)
else:
    print(dis[6][6])

7-10. 미로탐색

"""
미로의 최단거리
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 0 0 0

"""

dx=[-1,0,1,0]
dy=[0,1,0,-1]
def DFS(x,y):
    global cnt
    if x==6 and y==6:
        cnt+=1
    else:
        for i in range(4):
            xx=x+dx[i]
            yy=y+dy[i]
            if 0<=xx<=6 and 0<=yy<=6 and board[xx][yy]==0:
                board[xx][yy]=1
                DFS(xx,yy)
                board[xx][yy]=0

board=[list(map(int, input().split())) for _ in range(7)]
cnt=0
board[0][0]=1
DFS(0,0)

7-11. 등산 경로

"""
등산경로
값을 변경되는 방식은 BFS
"""

def DFS(x,y):
    global cnt
    if x == ex and y == ey:
        cnt+=1
    else:
        for k in range(4):
            xx=x+dx[k]
            yy=y+dy[k]
            if 0<=xx<n and 0<=yy<n and ch[xx][yy]==0 and board[xx][yy]>board[x][y]:
                ch[xx][yy]=1
                DFS(xx,yy)
                ch[xx][yy]=0

n = int(input())
board = [[0]*n for _ in range(n)]
ch = [[0]*n for _ in range(n)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
max = -1e9
min = 1e9
for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(n):
        if tmp[j]<min:
            min=tmp[j]
            sx=i
            sy=j
        if tmp[j]>max:
            max=tmp[j]
            ex=i
            ey=j
        board[i][j]=tmp[j]
    ch[sx][sy]=1
    cnt=0
    DFS(sx, sy)
    print(cnt)

7-12. 단지 번호 붙이기

"""
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
"""
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def DFS(x,y):
    global cnt
    cnt+=1
    board[x][y]=0
    for i in range(4):
        xx=x+dx[i]
        yy=y+dy[i]
        if 0<=xx<n and 0<=yy<n and board[xx][yy]==1:
            DFS(xx,yy)

n = int(input())
board = [list(map(int, input())) for _ in range(n)]
res=[]
for i in range(n):
    for j in range(n):
        if board[i][j]==1:
            cnt=0
            DFS(i, j)
            res.append(cnt)
print(len(res))
res.sort()
for x in res:
    print(x)

7-13. 섬나라 아일랜드
7-14. 안전영역