[백준 python] 1105번 팔 - 그리디 레벨: 실버1 언어: python 문제풀러가기 📑풀이 과정 이러한 문제는 예시를 몇개 넣어보면서 조건에 맞는것을 찾아보면 풀이 방법이 떠오른다. 핵심은 반드시 8이 들어가는 곳의 수를 찾아서 출력하면된다. 먼저 두 수의 자리수가 같은지 확인한다. 자리수가 다르면 무조건 0이 나올 수 밖에 없다. ex) 8 10 -> 9나 10이 선택 됨으로 무조건 0이 나옴 그리고 자리수가 같을 때는 앞자리부터 확인한다. 이때 앞자리가 같으면서 8인 경우가 8이 꼭 들어가야만 하는 자리이다. ex) 80 88 1개, 888 889 2개 앞 자리부터 공통으로 들어가는 8의 수를 확인 그리고 앞자리가 같으면서 8이 아닌 경우는 뒤에 8이 있는지 확인해야한다. ex) 1878 1..

[백준 python] 1246번 온라인 판매 레벨: 실버 5 언어: python 문제풀러가기 📑풀이 과정 들어온 가격을 내림차순으로 정렬하고 해당가격에 팔았을 때 값을 result 배열에 저장했다. for 문에서 i+1가 판매하는 인원 수 인데 이 값이 N을 넘어가면 break 걸었다. 그리고 result 배열에서 가장 큰 값을 출력하였다. 📋풀이 코드 import sys sys.stdin = open("input_py.txt", "r") input = sys.stdin.readline N ,M = map(int, input().split(' ')) arr = [int(input()) for _ in range(M)] arr.sort(reverse=True) result = [] for i..

[백준 python] 1449번 수리공 항승 - 그리디 레벨: 실버 3 언어: python 문제풀러가기 📑풀이 과정 물이 세는 곳 하나를 막기 위해서는 좌우 0.5 만큼이 필요하다 물이 세는 곳이 1이라면 0.5 ~ 1.5 구간이 테이프가 발리는 구간이다. 예시 처럼 테이프의 길이가 2이고 1 과 2 에서 물이 셀 때 0.5 ~ 2.5 까지 테이프를 붙여야하고 이때 길이 2짜리가 한개 들어간다. 물이 세는 곳의 입력을 배열에 저장하고 오름차순으로 정렬한다. 처음 들어오는 값을 기준으로 테이프를 처음 붙이는 곳 arr[0] - 0.5 -> start라는 변수에 저장 테이프가 끝나는 곳 start + L -> end라고 저장 arr 순회 하면서 start 보다 크고 end 보다 작은 값은 넘어가고 범위를 넘..

[백준 python] 18310번 안테나 - 그리디 레벨: 실버 3 언어: python 📑풀이 과정 1. 모든 경우 계산 처음 문제를 보고 모든 값 집의 위치 마다 거리를 계산 했다. 이 경우 n^2의 시간 복잡도를 가지는데 입력값의 최대가 200,000이라서 무조건 시간 초과가 나오게 된다. 2. 다른 풀이 수학적으로 생각하면 간단하게 풀 수 있는 문제이다. 모든 집까지의 거리의 총합이 가장 작으려면 일직선 상에서 가운데에 가까울 수록 총합이 적어진다. 그래서 배열에 집의 위치를 저장하고 정렬 후 중앙값을 찾아서 출력하면 된다. 📋풀이 코드 import sys input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split(' ..

[백준 python] 1448번 삼각형 만들기 - 그리디 레벨: 실버3 언어: python 문제풀러가기 📑풀이 과정 삼각형의 조건 중 가장 긴 변이 나머지 두변의 합보다 작다 라는 조건이 있다. 가장 긴변이 A라면 A < B + C 조건을 만족하면 된다. 들어오는 값을 정렬한 뒤 가장 큰 값, 두번째로 큰 값, 세번째로 큰값을 조건이 맞는지 비교하면 된다. 📋풀이 코드 import sys input = sys.stdin.readline def fun(arr): i = 0 while i+2

[백준 python] 9658번 돌 게임 4 - 동적프로그래밍 레벨: 실버2 언어: python 문제풀러가기 9658번: 돌 게임 4 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 📑풀이 과정 DP를 이용해서 풀이할 수 있는 문제이다. 나는 이 문제를 풀기 위해 돌이 N개 있을 때 후공자의 승패 여부를 dp 배열에 저장하고 사용하였다. dp[N]이 True 면 선공자의 승이면서 후공자의 패이다. 아래의 표와 같이 후공이 지고 이기는 상황을 알 수 있다. 이때 돌이 N개 일때 누가 이기는 알기 위해서 N - 1 일때 N - 3 일때 N - 4 일때 후공자가 승인지 패인지를 보면 현재 게임에서 누가 이기는지 알 수 있다. 상근이가 돌을 가져가는 갔을 때..

[백준 python] 2225번 합분해 - 동적프로그래밍(DP) 레벨: 골드 5 언어: python 문제풀러가기 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제설명 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력값 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력값 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 📑풀이 과정 DP 동적프로그래밍은 문제를 보고 식을 만들 수 있으면 쉽게 풀..

[백준 python] 2579번 계단 오르기 - 동적프로그래밍(DP) 레벨: 실버 3 언어: python 문제풀러가기 문제설명 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟..