developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 삼성코테파이썬
  • 통계분석
  • ARIMA모형
  • Arima
  • 삼성코테파이썬풀이
  • 백준파이썬풀이
  • 삼성코테자바풀이
  • 삼성코테구현풀이
  • c++디자인패턴
  • 삼성코테자바준비
  • 삼성코테기출
  • 카카오코테
  • 시계열
  • 삼성코테기출자바풀이
  • 삼성코테구현문제추천
  • BOJ파이썬풀이
  • 삼성코테자바꿀팁
  • AR모형
  • SW역량테스트파이썬풀이
  • c++ 빌더 패턴
  • 통계학
  • SW역량테스트파이썬
  • MA모형
  • 운영체제인터럽트
  • 시계열분석
  • 카카오코테java풀이
  • 삼성코테파이썬준비
  • 삼성코테준비
  • 코테파이썬
  • 데이터분석

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

SW Expert Academy - 벌꿀 채취 (python)

2021. 10. 23. 16:23

❓ 문제 - SW Expert Academy 벌꿀 채취 python 풀이법

 

출처 

(https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu)

 

 

 

📝 문제해결법

1. 이 문제는 DFS 2번+ 구현으로 풀었다.

  • 한사람이 벌꿀채취를 할 때 가로열의 맨 처음 인덱스는 (0 ~ n-m-1)까지 가능하므로 모든 행과 해당 열에 맞춰 두 사람에 대한 조합을 으로 두 사람이 벌꿀채취를 할 수 있는 경우의 수를 다 뽑는다.
  • 다음으로 두 사람에 대해 만약 같은 행인데, 두 사람이 벌꿀재취를 할 때 가로의 맨 처음 인덱스의 차이가 m 보다 작으면 둘이 겹치므로 해당 경우는 탐색하지 않고, 그 외의 경우에는 solve1()함수를 통해 꿀을 채취했을 때 얻을 수 있는 금액의 최대값을 갱신한다.
  • solve1() 함수에서 만약 벌꿀채취를 하려는 가로열의 합이 c보다 크다면 m개의 가로열중 최대 이윤을 남기는 일부만 채취할 수 있으므로 최대 이윤을 구하기 위해 solve2() 함수로 DFS를 돌린다.
  • solve2() 함수에는 현재까지 꿀을 채취한 양 summ, 현재까지 꿀을 채취한 양의 제곱의 합 result를 이용하는데 우선 summ이 c보다 크면 dfs 순회를 종료하고, 만약 마지막까지 열까지 순회를 했는데도 summ이 c보다 작다면 result인 이윤을 비교할 리스트에 넣어준다. 이외엔, 해당 열을 선택했을 때의 summ과 result 값으로  dfs를 돌리고, 해당 열을 선택하지 않았을 때 summ과 result 값으로 dfs를 돌린다.
  • 만약 벌꿀재취를 하려는 가료열의 합이 c보다 커서 solve2() 함수를 돌렸으면, 최대 이윤을 찾기위해 이윤들을 담은 리스트의 최대값을 한 사람의 최대이윤으로 선택해 더해준다.

2. 문제 풀면서 느낀점

  • 처음에 가로열의 합이 c보다 큰 경우, 내림차순해서 계속 더하면서 만약 c보다 더 크면 그 직전까지 제곱의 값을 더해서 최대이윤으로 정했는데, 그럼 7, 5, 5 에서 c=10일 때는 7^2 = 49로 최대이윤을 구하게되는데 , 사실 (5^2 + 5^2) = 50이 더 크므로 이 방법은 틀렸다. 따라서 DFS로 다시 최대이윤을 구할 수 있게 다른 사람의 코드를 참고해서 구현했다...
  • DFS + DFS 문제라니 ... 이런 문제도 접할 수 있어서 좋은 경험이었다. 다음에 이런 사소한 부분까지 잘 구현할 줄 아는 사람이 되자 !!

 

💻 소스코드

T = int(input())
def solve2(idx, a, summ, result):
    if summ > c:
        return
    if idx == len(a) and summ <= c:
        alst.append(result)
        return
    solve2(idx+1, a, summ+a[idx], result+a[idx]**2)
    solve2(idx+1, a, summ, result)

def solve(c1, c2):
    arr1 = []
    arr2 = []
    money = 0
    global alst
    for j in range(m):
        arr1.append(board[c1[0]][c1[1]+j])
        arr2.append(board[c2[0]][c2[1]+j])
    if sum(arr1) > c:
        alst = []
        solve2(0, arr1, 0, 0)
        money += (max(alst))
    else:
        for a in arr1:
            money += (a*a)

    if sum(arr2) > c:
        alst = []
        solve2(0, arr2, 0, 0)
        money += (max(alst))
    else:
        for a in arr2:
            money += (a * a)
    return money

def combination(lst, num):
    result = []
    if num > len(lst):
        return result
    if num == 1:
        for l in lst:
            result.append([l])
    elif num > 1:
        for i in range(len(lst)-num+1):
            for temp in combination(lst[i+1:], num-1):
                result.append([lst[i]]+temp)
    return result

for test_case in range(1, T+1):
    n, m, c = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(n)]
    c_lst = []
    for i in range(n):
        for j in range(n):
            if j+(m-1) > n-1:
                break
            c_lst.append([i, j])
    answer = -1

    for com in list(combination(c_lst, 2)):
        if com[0][0] == com[1][0] and abs(com[0][1]-com[1][1]) < m:
            continue
        answer = max(answer, solve(com[0], com[1]))
    print(f'#{test_case} {answer}')

 

 

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 시간 관리 1263번 (JAVA)  (0) 2022.01.24
SW Expert Academy - 등산로 조정 (python)  (0) 2021.10.23
SW Expert Academy - 보호 필름 (python)  (0) 2021.10.23
SW Expert Academy - 디저트카페 (python)  (0) 2021.10.22
SW Expert Academy - 수영장 (python)  (0) 2021.10.22
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 시간 관리 1263번 (JAVA)
    • SW Expert Academy - 등산로 조정 (python)
    • SW Expert Academy - 보호 필름 (python)
    • SW Expert Academy - 디저트카페 (python)
    developer-ellen
    developer-ellen

    티스토리툴바