Notice
Recent Posts
Recent Comments
Link
«   2025/06   »
일 월 화 수 목 금 토
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30
Tags more
Archives
Today
Total
관리 메뉴

:)

[백준]꽃길, [백준]도영이가 만든 맛있는 음식, [백준]부분 삼각 수열 본문

Algorithm(python)

[백준]꽃길, [백준]도영이가 만든 맛있는 음식, [백준]부분 삼각 수열

mihee 2022. 10. 5. 16:41

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

 

14620번: 꽃길

2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므

www.acmicpc.net

완전탐색

1) 0 < i < 6, 0 < j < 6, (i,j) 비용 구하기

2) combination 조합을 구함

3) combination 후보가 꽃길이 성립되는지 확인((i,j) 기준으로 차이가 abs 3이상)

 

import sys
from itertools import combinations

def solution(N,arr):
    ans = float('inf')
    
    def get_cost(i,j):
        return (arr[i+1][j] + arr[i-1][j] + arr[i][j] + arr[i][j+1] + arr[i][j-1])

    def collide(coor1, coor2):
        return abs(coor1[0]-coor2[0]) + abs(coor1[1] - coor2[1]) <=2 
    prices = {(i,j):get_cost(i,j) for i in range(1, N-1) for j in range(1, N-1)}
    # print(prices)
    
    for choices in combinations(prices, 3):
        for pair in combinations(choices,2):
            if collide(*pair):
                break
        else:
            ans = min(ans, sum(prices[coor] for coor in choices))     
    return ans
    
        
N = int(sys.stdin.readline())
arr = [list(map(int, row.split())) for row in sys.stdin.readlines()]
      
print(solution(N, arr))

 

 

 

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

 

2961번: 도영이가 만든 맛있는 음식

첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은

www.acmicpc.net

완전탐색

1) combination 조합 구하기

2) diff 차이 계산

 

import sys
from itertools import combinations

def solution(N, arr):
    ans = float('inf')

    def diff(foods):
        s,b = 1,0
        for _s,_b in foods:
            s *= _s
            b += _b
        return abs(s-b)
    
    for i in range(1, N+1):
        for choice in combinations(arr, i):
            ans = min(ans, diff(choice))
    return ans
            
N = int(sys.stdin.readline())
arr = [list(map(int, row.split())) for row in sys.stdin.readlines()]

print(solution(N,arr))

 

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

 

1548번: 부분 삼각 수열

세 수 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다. 마찬가지로 길이가 N인 수열 B(b[0], b[1], ..., b[n-1])의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 이 수열은 삼각

www.acmicpc.net

완전탐색

B = {b1, b2, b3, .... , bn}   -> 정렬 (b1<=b2<=b3<...<=bn)

b1 + b2 > bn 이면 그 사이 bk값들은 부분 삼각 수열 성립

 

import sys

def solution(N, nums):
    nums.sort()
    for n in range(N, 0, -1):
        for i in range(N - n + 1):
            if n < 3 or nums[i] + nums[i+1] > nums[i+n-1]:
                return n
            
N = int(sys.stdin.readline())
nums = [int(n) for n in sys.stdin.readline().split()]
print(solution(N, nums))
저작자표시 (새창열림)

'Algorithm(python)' 카테고리의 다른 글

[프로그래머스]신고 결과 받기, [프로그래머스]양궁대회  (0) 2022.10.08
[프로그래머스]튜플, [프로그래머스]스킬트리  (0) 2022.10.05
[백준] 오리, [백준] 달력  (0) 2022.09.28
정규표현식, [백준]단어뒤집기2  (1) 2022.09.21
python 문법 for algorithm  (0) 2022.08.02
'Algorithm(python)' Related Articles more
Comments