[2023 알고리즘 스터디] 4조 이은선 2주차 - 백준 11508, 19941, 16953, 1080

(1) [백준] 11508번 : 2+1 세일 (파이썬)

 

그리디 알고리즘 문제

 

(1) 처음 내 코드 (성공)

n=int(input())
price=[]
cost=0
for _ in range(n):
    a=int(input())
    price.append(a)
price.sort(reverse=True)

if len(price)<3:
    for i in price:
        cost+=i
else:
    for i in range(len(price)):
        if ((i+1)%3==0):
            continue
        else:
            cost+=price[i]
print(cost)

처음에, 구매하려는 유제품 갯수가 3개 미만일 때와 그 이상일 때의 경우로 케이스를 나눴다.

 

(1) 유제품 갯수가 3개 미만일 때

그냥 모든 값을 더해주면 된다. 

 

(2) 유제품 갯수가 3개 이상일 때

우리는 최소 비용으로 2+1 유제품을 구매하려는 게 목적이다. 

예를 들어서 6개의 유제품을 구매하려고 할 때, 그 가격이 각각 6,5,4,3,2,1원이라면 우리는 (6,5,4),(4,3,2),(1) 이렇게 묶어주는게 가장 효율적이다. 즉, 유제품의 가격이 들어있는 리스트를 정렬 후에 2(3-1),5(6-1)번째 인덱스의 유제품만 전체 비용에서 제외시켜주면 되는 것이다.

 

위와 같은 풀이로 성공은 했지만, 시간을 보니 4052ms나 걸렸다. 내 생각에 for문 안에서 (index+1)%3을 매번 계산하는 코드가 시간을 많이 잡아먹은 것 같다. 따라서 이 부분을 최적화해서 다시 풀어보았다.

 

(2) 최적화 후 내 코드

import sys
input = sys.stdin.readline
n=int(input())

price = [int(input()) for _ in range((n))]
price.sort(reverse=True)
cost = sum(price)

for i in range(2,n,3):
    cost-=price[i]

print(cost)

 

(2) [백준] 19941번 : 햄버거 분배 (파이썬)

 

그리디 알고리즘 문제

 

ex)

input 

12 2
HPHPHPHHPPHP

output 

6

 

(1) 처음 내 코드 (실패)

a,b=map(int,input().split())
ham = list(input()) # H P
cnt=0

for i in range(len(ham)):
    if ham[i]=="P":
        change=False
        for j in range(i-b,i,1):
            if j<0 or j>=a:
                continue
            else:
                if ham[j]=="H":
                    ham[j]="O"
                    change=True
                    cnt+=1
                    break
        if change==False:
            for j in range(i+b,i,-1):
                if j<0 or j>=a:
                    continue
                else:
                    if ham[j]=="H":
                        ham[j]="O"
                        change=True
                        cnt+=1
                        break
        

print(cnt)

list 값이 "P"라면 양옆에 값을 모두 확인해가면서 "H"를 찾아야 한다. 그리고, 한번 사용된 "H"는 다시 사용되면 안되므로 이 값을 다른 값으로 바꿔주어야 한다. 한 번 쓰인 햄버거는 이미 썼다는 뜻을 담아 "O"의 값을 갖도록 바꿔주었다.

처음 내 코드는 사용하지 않은 햄버거라면 가능한 가장 먼 거리의 햄버거부터 사용하도록 코드를 짰다. 또, "P"의 왼쪽 값부터 확인하여 "P"의 왼쪽에서 햄버거를 찾는다면 그 값을 사용해주었고, 왼쪽에서 햄버거가 발견되지 않는다면 "P"의 오른쪽 값도 확인하여 햄버거를 사용하게끔 코드를 짜주었다. change라는 bool 변수를 두어, 왼쪽에서 햄버거를 찾아서 사용했는지 여부를 저장해주었다.

결론은 실패하였다. 반례가 될만 한 케이스들은 거의 모두 해봤는데, 어디가 정확히 문제인진 찾지 못했다. 뒤에 있는 "P"도 고려하며 햄버거를 사용하지 않은 것이 문제일까? 아무튼 정확한 이유는 찾지 못했다.

 

(2) 코드 수정 후 내 코드 (성공)

a,b=map(int,input().split())
ham = list(input()) # H P
cnt=0

for i in range(len(ham)):
    if ham[i]=="P":
        for j in range(i-b,i+b+1,1):
            if j<0 or j>=a:
                continue
            else:
                if ham[j]=="H":
                    ham[j]="O"
                    cnt+=1
                    break
print(cnt)

일단, 위의 (1)번 코드에서 불필요하게 case를 두개로 나누어 for문을 돌 필요가 없다는 생각이 들어, 코드 최적화를 진행해주었다. 그 후에 혹여나 하는 마음으로 재제출을 해보았는데, 성공하였다. 

 

(3) [백준] 16953번 : A → B (파이썬)

 

BFS 문제

 

 

(1) 처음에 내가 생각한 방식

 

#BFS
from collections import deque
import math
a,b=map(int,input().split())
queue = deque()
count=[]
ans=0

queue.append(a)
index=0
while queue:
    index+=1
    q = queue.popleft()
    if q==b:
        ans=math.ceil(math.sqrt(index))
        break
    queue.append(q*2)
    queue.append(int(str(q)+str("1")))

print(ans)

 

처음에 이 문제를 보자마자 나는 위와 같은 방식으로 풀었다. 하지만, 예제 입력 1이나 예제 입력 3처럼 공백을 기준으로 입력 받은 왼쪽 값에서 오른쪽 값으로 갈 수 있는 경우만 고려한 방식이었다. 즉, 예제 입력 2처럼 공백을 기준으로 입력 받은 왼쪽 값에서 오른쪽 값으로 갈 수 없는 경우는 고려하지 않은 코드였다. 위와 같은 코드는 예제 입력 2와 같은 입력이 들어왔을 경우, break문을 만나지 못하므로 무한 루프에 걸리는 코드이다. 처음에 직관적으로 짠 코드라서 이와 같은 예제는 고려하지 못하였었다.

 

ex) 2 162

# 2 → 4 → 8 → 81 → 162

 

2 

4 21 [2] 1

21 8 41 [4] 2

8 41 42 211 [21] 3

41 42 211 16 81 [8] 4

42 211 16 81 82 411 [41] 5

211 16 81 82 411 84 421 [42] 6

16 81 82 411 84 421 422 2111 [211] 7

81 82 411 84 421 422 2111 32 161 [16] 8

411 84 421 422 2111 32 161 162 811 [81]

 

-> (1)과 같은 방식으로 풀었을 때에 queue에 저장되는 값을 나열한 것이다. []안의 값은 queue에서 pop한 값이고, 파란색 글씨 부분이 index 변수 값을 의미한다. 우리는 queue에서 값을 하나 꺼내고, 값을 두개 넣어줄 때마다 index를 1씩 증가시킨다. 여기선, index의 제곱근을 올림한 값을 출력값으로 지정했는데, 문제가 있다.

다음 예를 들어 설명해보겠다.

input : 2 8 ---> index 값은 4이므로 제곱근은 2이다. 2->4->8 (실제값 : 2) O

input : 2 81 ---> index 값은 9이므로 제곱근은 3이다. 2->4->8->81 (실제값 : 3) O

input: 2 42 ---> index값은 6이므로 제곱근을 올림한 값은 3이다. 2->21->42 (실제값 : 2) X

 

이렇게 만족하지 않는 예시도 존재한다. 따라서, 이 문제에서 위와 같이 index를 따로 도입하고, 제곱근을 사용하는 것은 올바르지 못한 선택이었다.

 

(2) 코드 수정 후 내 코드 (성공)

 

#BFS
from collections import deque
import math
a,b=map(int,input().split())
queue = deque()
ans=-1

queue.append((a,1))
index=0
while queue:
    q,cnt = queue.popleft()
    if q==b:
        ans=cnt
        break
    if q>b:
        continue
    queue.append((q*2,cnt+1))
    queue.append((int(str(q)+str("1")),cnt+1))

print(ans)

 

일단, (1)에서의 방식처럼 불필요하게 index란 변수를 도입할 필요가 없기 때문에 이 부분을 수정해주었다. index 변수를 사용하여 출력값을 위한 준비를 따로 해주다 보면 어디선가 예기치 못한 변수가 발생할 수도 있다. 따라서, 처음에 queue에 append 해줄 때 set 형식으로 값을 추가해주었다. 또, 공백을 기준으로 오른쪽으로 입력 받은 값보다 queue에서 꺼낸 값이 더 크다면 continue를 사용하여, queue에 append하는 부분을 제외시켜주었다. 이로서, 무한루프 또한 벗어날 수 있게 되었다.

 

(4) [백준] 1080번 : 행렬 (파이썬)

N, M = map(int, input().split())
A = [list(map(int, list(input()))) for _ in range(N)]
B = [list(map(int, list(input()))) for _ in range(N)]

cnt = 0

def check():
    for i in range(N):
        for j in range(M):
            if A[i][j] != B[i][j]:
                return False
    return True

def solve(x, y):
    for i in range(x, x+3):
        for j in range(y, y+3):
            A[i][j] = 1 - A[i][j] 

for i in range(0, N-2):  
    for j in range(0, M-2):  
        if A[i][j] != B[i][j]:
            cnt += 1
            solve(i,j)

if check():
    print(cnt)
else:
    print(-1)

3x3 행렬이므로 범위는 다음과 같다. i와 j값을 하나씩 늘려가며 모든 행렬 값을 확인한다. 마지막에는 A행렬과 B행렬이 같은지를 확인하고 같다면 solve() 함수를 몇번 호출했는지를, 다르다면 -1의 값을 반환한다.