[2023 알고리즘 스터디] 4조 #1주차 - 백준 3085번(사탕 게임), 24954번(물약 구매) 문제 풀이

[2023 알고리즘 스터디] 4조 #1주차- (알고리즘 성능평가 & Python 문법) 학습 및 백준 3085번(사탕 게임), 24954번(물약 구매) 문제풀이

 

사탕게임

 

- 문제 링크

https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

 

-    문제 간단 설명

 N x N 크기의 사탕 게임 판이 주어지고 인접한 두 사탕을 고르고 바꾼다 (한번)

그리고 연달아 있는 사탕을 모두 먹는 게임이다.

가장 많이 먹을 수 있는 사탕의 수를 출력해 보아라.

 

- 예제 입력 1

3
CCP
CCP
PPC

- 예제 입력 2

4
PPPP
CYZY
CCPY
PPCC

- 예제 입력 3

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

- 예제 입출력 정리

 

 

- 전체 코드

import sys
input = sys.stdin.readline

def check(lst):
    res = 1
    for i in range(len(lst)):

        # 가로로 같은 색이 연달아서 나오는 경우 확인
        cnt = 1
        for j in range(1, len(lst)):
            if lst[i][j] == lst[i][j-1]:
                cnt += 1
                res = max(cnt, res)
            else:
                cnt = 1

        # 세로로 같은 색이 연달아서 나오는 경우 확인.
        cnt = 1
        for j in range(1, len(lst)):
            if lst[j][i] == lst[j-1][i]:
                cnt += 1
                res = max(cnt, res)
            else:
                cnt = 1
    return res

n = int(input())
og_list = [list(input().rstrip()) for _ in range(n)]
res = 0

for i in range(n):

    for j in range(n):
        if j+1 < n: # 인덱싱 잡아주기

            # 가로로 바꿔주고 check() 함수 사용해서 몇개인지 확인하고
            og_list[i][j], og_list[i][j+1] = og_list[i][j+1], og_list[i][j]
            tmp_res = check(og_list)

            #가장 큰 값을 res 값으로.
            if tmp_res > res:
                res = tmp_res

            #다시 원래대로 바꿔주고
            og_list[i][j], og_list[i][j+1] = og_list[i][j+1], og_list[i][j]

        if i+1 < n:

            # 세로 방향으로 바꿔주고, check() 함수 사용해서 몇개인지 확인하고
            og_list[i][j], og_list[i+1][j] = og_list[i+1][j], og_list[i][j]
            tmp_res = check(og_list)

            # 더 큰값을 res가 받도록 한다.
            if tmp_res > res:
                res = tmp_res

            # 다시 원래대로 돌려주기
            og_list[i][j], og_list[i+1][j] = og_list[i+1][j], og_list[i][j]
print(res)

 

- 코드 분석

    함수 check():

 2차원 배열(사탕게임 판)을 가로로, 세로로 돌면서 연달아서 나오는 가장 큰 값을 반환하는 함수

def check(lst):
    res = 1
    for i in range(len(lst)):

        # 가로로 같은 색이 연달아서 나오는 경우 확인
        cnt = 1
        for j in range(1, len(lst)):
            if lst[i][j] == lst[i][j-1]:
                cnt += 1
                res = max(cnt, res)
            else:
                cnt = 1

        # 세로로 같은 색이 연달아서 나오는 경우 확인.
        cnt = 1
        for j in range(1, len(lst)):
            if lst[j][i] == lst[j-1][i]:
                cnt += 1
                res = max(cnt, res)
            else:
                cnt = 1
    return res

 

    실제 코드 실행부분:

 N 을 입력받아서 N x N 사탕 배열을 만들고

n = int(input())
og_list = [list(input().rstrip()) for _ in range(n)]
res = 0

 

 

 배열을 돌면서 가로로 한번 바꿔보고 그랬을 때의 가장 사탕을 많이 먹을 수 있는 값을 check() 함수로 확인한다.

for i in range(n):

    for j in range(n):
        if j+1 < n: # 인덱싱 잡아주기

            # 가로로 바꿔주고 check() 함수 사용해서 몇개인지 확인하고
            og_list[i][j], og_list[i][j+1] = og_list[i][j+1], og_list[i][j]
            tmp_res = check(og_list)

그리고 방금 실행한 값이 이전의 최댓값보다 크면 값을 업데이트 해준다.

            #가장 큰 값을 res 값으로.
            if tmp_res > res:
                res = tmp_res

후에 바꾼 배열을 원상복구 시켜준다.

            #다시 원래대로 바꿔주고
            og_list[i][j], og_list[i][j+1] = og_list[i][j+1], og_list[i][j]

가로 방향으로 전부 실행을 한다.

 

세로 방향도 마찬가지로 실행한다.

        if i+1 < n:

            # 세로 방향으로 바꿔주고, check() 함수 사용해서 몇개인지 확인하고
            og_list[i][j], og_list[i+1][j] = og_list[i+1][j], og_list[i][j]
            tmp_res = check(og_list)

            # 더 큰값을 res가 받도록 한다.
            if tmp_res > res:
                res = tmp_res

            # 다시 원래대로 돌려주기
            og_list[i][j], og_list[i+1][j] = og_list[i+1][j], og_list[i][j]
print(res)

 

물약 구매

 

- 문제 링크

https://www.acmicpc.net/problem/24954

24954번: 물약 구매

 

(문제를 이해하고, 예제 입출력만 이해한다면 반 이상은 푼 것이다)

-    문제 간단 설명:

 N 개의 물약이 있고, original price가 정해져 있다. 상점에서 특별 이벤트를 하고 있고, 특정물약(ex)1번물약)을 구매하면 2개의

할인 정보가 있고 그것은 (3번 물약을 10원 할인, 2번 물약을 20원 할인) 해준다는 이야기이다. 하지만 2번 물약의 원래 가격(15)보다

많이 할인이 들어가있는 경우에는  1원은 결제해야한다.

  모든 물약을 다 사도 물건을 구매하는 순서에 따라 총 금액이 달라진다.

 

출력으로는 가장 싸게 샀을 때의 비용을 출력한다.

 

-    문제 해결:

  물약을 모두 사는 경우의 수를 case_list에 담고, 그것을 모두 실행했을 때 가장 싼 값을 결과로 출력하자.

 

- 예제 입력 & 출력

# 예제 입력
4
10 15 20 25
2
3 10
2 20
0
1
4 10
1
1 10

# 예제 출력
36

 

 

 

- 전체 코드

import sys
from itertools import permutations

N = int(sys.stdin.readline().rstrip())

# 원래 가격, 할인정보, 가능한 모든 case 순서, res는 가장 작은 값으로 향하도록 만드는데, 모두 할인 안받고 사는 가격으로 초기설정
og_price = list(map(int, sys.stdin.readline().split()))
sales_list = [[] for _ in range(N)]
cases_list = permutations(range(0,N), N) #num of cases
res = sum(og_price)

for i in range(N):
    tmp_num = int(sys.stdin.readline().rstrip())
    for j in range(tmp_num):
        tmp_sales = list(map(int, sys.stdin.readline().split()))
        sales_list[i].append(tmp_sales)

for i in cases_list: # [ 1, 2, 3, 4]
    tmp_price = og_price[:]
    tmp_res = 0

    # ex) 1, 2, 3, 4, 번 물약을 순서대로 구매했을 때
    for j in i:
        tmp_res += tmp_price[j]
        for a, d in sales_list[j]: #a는 할인품목, d는 그 품목의 할인가격
            tmp_price[a-1] = max(1, tmp_price[a-1]-d) #할인받은 금액으로 구매(1원보다 작아질 수는 없기 때문에)

    # case 1개를 지났을 때 나오는 가격인 tmp_res가 현재 이전까지 계산된 가격중에 제일 싼 것보다도 싸면 그것을 채택
    res = min(res, tmp_res)

print(res)

 - 코드 분석

 

og_price, cases_list, res, sales_list를 만들어준다.

import sys
from itertools import permutations

N = int(sys.stdin.readline().rstrip())

# 원래 가격, 할인정보, 가능한 모든 case 순서, res는 가장 작은 값으로 향하도록 만드는데, 모두 할인 안받고 사는 가격으로 초기설정
og_price = list(map(int, sys.stdin.readline().split()))
sales_list = [[] for _ in range(N)]
cases_list = permutations(range(0,N), N) #num of cases
res = sum(og_price)

for i in range(N):
    tmp_num = int(sys.stdin.readline().rstrip())
    for j in range(tmp_num):
        tmp_sales = list(map(int, sys.stdin.readline().split()))
        sales_list[i].append(tmp_sales)

 

  cases_list를 돌아다니면서, i는(0, 1, 2, 3)과 같은데, 순서대로 할인을 받으며 총 구매 금액을 tmp_res로 받아서 가장 작은 값을 res가 반환하도록 하여 출력한다.

for i in cases_list: # [0, 1, 2, 3]
    tmp_price = og_price[:]
    tmp_res = 0

    # ex) 1, 2, 3, 4, 번 물약을 순서대로 구매했을 때
    for j in i:
        tmp_res += tmp_price[j]
        for a, d in sales_list[j]: #a는 할인품목, d는 그 품목의 할인가격
            tmp_price[a-1] = max(1, tmp_price[a-1]-d) #할인받은 금액으로 구매(1원보다 작아질 수는 없기 때문에)

    # case 1개를 지났을 때 나오는 가격인 tmp_res가 현재 이전까지 계산된 가격중에 제일 싼 것보다도 싸면 그것을 채택
    res = min(res, tmp_res)

print(res)