본문 바로가기
728x90

PYTHON

[백준][파이썬] 2579 계단 오르기
백준 문제풀이 2023. 2. 15. [백준][파이썬] 2579 계단 오르기 1.문제 분석 동적 프로그래밍을 활용하는 문제 계단에 쓰인 숫자의 합을 최대로 하는 문제 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 2. 기본 아이디어 1,2,3 번째 계단까지 미리 합을 구해 score에 넣어둔다. 이후 맨 마지막 계단을 밟아야 한다라는 조건에 맞춰 max함수를 통해 2가지 경우 중 최대 값을 고른다. 3.문제 풀이 앞서 말했듯 마지막 계단을 밟는다는 조건에는 2가지 경우가 있다. 첫째, 맨 위에서 두번째 계단을 밟는 경우 둘째, 맨위에서 세번째 계단을 밟는 경..
[백준][파이썬] 1932 정수 삼각형
백준 문제풀이 2023. 2. 15. [백준][파이썬] 1932 정수 삼각형 1.문제 분석 정수 삼각형을 내려오면서 최대 합을 구하는 문제 동적 프로그래밍을 활용하는 문제 2. 기본 아이디어 정수 삼각형의 각 층에서 max함수를 활용해 최대값을 구한다. 2차원 리스트로 정수 삼각형을 구현한다. 3.문제 풀이 이 문제의 경우 정수 삼각형이 주어지기 때문에 숫자의 위치에 따라 위에서 받아올 수 있는 숫자가 달라진다. 예를 들어 이 삼각형의 경우 위에서부터 3층에 8, 1, 0 이 있는데 8로 내려올 경우 자신과 같은 tri[i - 1][0] 위치의 3을 더할 수 밖에 없고 0의 경우도 tri[i - 1][j - 1] 위치의 8만 더할 수 있다. 하지만 1의 경우 tri[i - 1][j - 1], tri[i - 1][j] 중 더 큰 값을 고르게 할 수 있다. 이후 맨 아래까지 내려왔을..
백준 문제풀이 2023. 2. 15. [백준][파이썬] 2563 색종이 1.문제 분석 2차원 배열을 활용하는 문제 2차원 넓이를 구하는 문제 2. 기본 아이디어 2차원 배열의 각 원소가 색종이의 넓이를 나타내도록 한다. 색종이가 붙여진 곳이라면 1, 아니라면 0을 넣는다. 3.문제 풀이 도화지의 넓이를 2차원 리스트로 구현한다. 색종이의 넓이는 가로, 세로 모두 10이다. 색종이의 왼쪽 아래 꼭짓점의 좌표가 주어지므로, x, y에 각각 10을 더해 색종이의 넓이를 구현한다. 코드로 구현 n = int(input()) confetti = 0 # 색종이의 넓이 pallete = [[0 for i in range(101)] for j in range(101)] # 도화지 for i in range(n): x, y = map(int, input().split()) for j in ..
[백준][파이썬] 13305 주유소
백준 문제풀이 2023. 2. 8. [백준][파이썬] 13305 주유소 1.문제 분석 도시들의 기름값과 거리를 바탕으로, 마지막 도시까지 가는 데 드는 기름값을 최소로 만드는 문제 서브태스크 문제 그리디 알고리즘을 활용하는 문제 (각 도시 사이의 거리가 2, 3, 1 이고 기름값이 각각 5, 2, 4, 1인 예시) 번호배점제한 1 17 모든 주유소의 리터당 가격은 1원이다. 2 41 2 ≤ N ≤ 1,000, 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 최대 10,000, 리터 당 가격은 최대 10,000이다. 3 42 원래의 제약조건 이외에 아무 제약조건이 없다. 2. 기본 아이디어 각 도시마다의 기름값을 비교한다. 비용들을 더하여 최솟값을 찾는다. 3.문제 풀이 코드로 구현 서브태스크 (17점) n = int(input()) road = list(map(int, i..
백준 문제풀이 2023. 2. 8. [백준][파이썬] 1541 잃어버린 괄호 1.문제 분석 괄호를 적절한 위치에 넣어서 식의 값을 최소로 만드는 문제 문자열을 숫자로 바꾸는 문제 2. 기본 아이디어 마이너스( - )를 기준으로 식을 자른다. 덧셈부분은 그대로 int형으로 바꾸어 더한다. 뺄셈을 진행한다. 3.문제 풀이 코드로 구현 exp = input().split('-') # 마이너스를 기준으로 식을 분리하기 nums = [] for num in exp: sums = 0 a = num.split('+') # 덧셈 진행 for i in a: sums += int(i) nums.append(sums) b = nums[0] for i in range(1, len(nums)): # 뺄셈 진행 b -= nums[i] print(b)
백준 문제풀이 2023. 2. 8. [백준][파이썬] 2566 최댓값 1.문제 분석 9x9 격자판에서 최댓값을 찾는 문제 최댓값의 위치를 찾는 문제 2. 기본 아이디어 2차원 배열이므로 이중 for문을 활용한다. 3.문제 풀이 코드로 구현 최댓값과 그 위치를 이중 for문과 if문으로 찾는다. lst = [] for i in range(9): lst.append(list(map(int, input().split()))) maximum = 0 x, y = 0, 0 for i in range(9): for j in range(9): if(maximum < lst[i][j]): maximum = lst[i][j] x = i y = j print(maximum) print(x+1, y+1)
백준 문제풀이 2023. 2. 8. [백준][파이썬] 14889 스타트와 링크 1.문제 분석 각 팀의 시너지 차이가 최소가 되도록 팀을 나누는 문제 백트래킹 활용 문제 2. 기본 아이디어 스타트 팀에 팀원을 배정하고 나머지 인원을 링크팀으로 배정한다. 차이를 계산한 후 다시 dfs를 진행한다. 3.문제 풀이 코드로 구현 def calcul(): # 시너지 계산 함수 global ans start_p, link_p = 0, 0 for i in range(n): if i not in s_team: l_team.append(i) for i in range(n//2 - 1): for j in range(i+1, n//2): start_p += player[s_team[i]][s_team[j]] + player[s_team[j]][s_team[i]] link_p += player[l_tea..
백준 문제풀이 2023. 2. 8. [백준][파이썬] 14888 연산자 끼워넣기 1.문제 분석 N개의 숫자 사이에 N-1개의 연산자를 넣어 최대, 최소 연산값을 만드는 문제 주어진 수의 순서는 바꿀 수 없고, 나눗셈은 몫만 취한다. 연산 규칙을 무시하고 앞에서부터 계산한다. 백트래킹 활용 문제 2. 기본 아이디어 연산자를 입력받아 각각의 연산자마다 탐색을 진행한다. 1부터 n까지, 탐색을 끝마치면 최대, 최솟값을 저장한다. 3.문제 풀이 코드로 구현 n = int(input()) lst = list(map(int, input().split())) add, sub, multi, div = map(int, input().split()) max_sum = -1000000000 min_sum = 1000000000 def backTracking(cnt, ans): global max_sum..
백준 문제풀이 2023. 2. 4. [백준][파이썬] 1931 회의실 배정 1.문제 분석 최대 회의실 사용 수를 구하는 문제 그리디 알고리즘과 정렬을 사용하는 문제 2. 기본 아이디어 입력받은 회의실 사용시간을 시작,끝 시간을 기준으로 정렬한다. 현재 회의가 끝난 이후 가장 빠른 시작시간을 가진 회의를 배정한다. 3.문제 풀이 람다식을 활용하여 리스트를 시작시간, 끝시간을 기준으로 두 번 정렬했다. 이렇게, 최대한 빨리 시작해서 최대한 빨리 끝나는 시간 리스트를 만들게 됐다. 이제 눈 앞의 최적 회의를 고르고 카운트하면 된다. n = int(input()) lst = [] for i in range(n): lst.append(list(map(int, input().split()))) lst.sort(key= lambda x: x[0]) # 정렬 lst.sort(key= lamb..
728x90

티스토리툴바