[백준 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] 2644번 촌수 계산 DFS 레벨: 실버2 언어: 파이썬 문제풀러가기 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 문제 설명 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버..

백준 1012번 유기농 배추 레벨: 실버2 언어: python 문제풀러가기 문제설명 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는..