목록백준 (26)
나의 개발일지
[백준] 1417 국회의원 선거 [Python, 파이썬]
문제 : https://www.acmicpc.net/problem/1417 그리디, 최대 힙 사용 from heapq import heapify n = int(input()) dasom = int(input()) heap = [-int(input()) for _ in range(n-1)] # 최대 힙 구현을 위해 -를 붙여 저장 cnt = 0 heapify(heap) if n == 1: print(0) exit() while dasom
[백준] 1388 바닥 장식 [Python, 파이썬]
문제 : https://www.acmicpc.net/problem/1388 전체 타일의 개수 n*m에서 연결된 타일의 수를 빼주었다. n, m = map(int, input().split()) lst = [list(input()) for _ in range(n)] answer = n * m for i in range(n): for j in range(m): if j != m-1 and lst[i][j] == "-" and lst[i][j+1] == "-": answer -= 1 if i != n-1 and lst[i][j] == "|" and lst[i+1][j] == "|": answer -= 1 print(answer)
[백준] 16173 점프왕 쩰리(Small) [Python, 파이썬]
문제 : https://www.acmicpc.net/problem/16173 BFS 한 칸씩 이동이 아닌 현재 위치에 적혀있는 숫자만큼 이동을 시키는 문제 (오른쪽, 아래로만) from collections import deque n = int(input()) Map = [list(map(int, input().split())) for _ in range(n)] visit = [[0] * n for _ in range(n)] visit[0][0] = 1 q = deque([(0, 0)]) while q: x, y = q.popleft() mx, my = [0, Map[x][y]], [Map[x][y], 0] # 현재 위치에 적힌 숫자만큼 이동 if x == n-1 and y == n-1: print("H..
[백준] 17202 핸드폰 번호 궁합 [Python, 파이썬]
문제 : https://www.acmicpc.net/problem/17202 DP 두 개의 번호를 풀이에 맞는 형태로 하나의 dp 리스트에 담는다. 점화식 : dp[i] = (dp[i] + dp[i+1]) % 10 dp.pop()으로 맨 뒤의 요소를 뺀다. 두 자리가 완성되면 종료, 출력 a = list(map(int, input())) b = list(map(int, input())) dp = [] for i in range(8): dp.append(a[i]) dp.append(b[i]) while len(dp) != 2: for i in range(len(dp)-1): dp[i] = (dp[i] + dp[i+1]) % 10 dp.pop() print(dp[0], end="") print(dp[1])
[백준] 24416 알고리즘 수업 - 피보나치 수 1 [Python, 파이썬]
문제 : https://www.acmicpc.net/problem/24416 피보나치 수를 직접 재귀를 구현해서 풀면 시간초과가 뜬다. n에 해당하는 피보나치 수를 재귀로 구한 값과 재귀가 호출된 횟수는 같아서 dp로 얻은 값을 리턴함 n = int(input()) def dp_fibo(n): dp = [1, 1] cnt = 0 for i in range(2, n): dp.append(dp[i-2]+dp[i-1]) cnt += 1 return print(dp[n-1], cnt) dp_fibo(n)
[백준] 1477 휴게소 세우기 [Python, 파이썬]
문제 : https://www.acmicpc.net/problem/1477 이분탐색 n, m, l = map(int, input().split()) li = list(map(int, input().split())) li.append(0) # 처음 li.append(l) # 끝 li.sort() dist = [] # 휴게소 사이의 거리를 담을 배열 for i in range(1, len(li)): dist.append(li[i]-li[i-1]-1) # 시작이 1부터라서 거리 구하고 1을 뺀다 dist.sort() l, r = 1, l answer = 1001 while l m: # 개수가 많으면 l = mid + 1 # 크기를 늘린다. else: answer = min(answer, mid) # 가능한 값..
[백준] 1111번 IQ Test [Python, 파이썬]
문제 : https://www.acmicpc.net/problem/1111 완전 탐색 알고리즘 예외) A인 경우 n == 1 n == 2 and 두 수가 다른 경우 반복문 i와 j의 범위는 질문 게시판을 통해 알아냄.. n = int(input()) test = list(map(int, input().split())) if n == 2 and test[0] != test[1] or n == 1: print('A') exit() for i in range(-200, 201): for j in range(-20000, 20001): if test[0] * i + j == test[1]: sw = 0 for k in range(n-1): if test[k] * i + j != test[k+1]: sw = 1 ..
[백준] 13305번 주유소 [Python]
문제 : https://www.acmicpc.net/problem/13305 Greedy Algorithm n = int(input()) road = list(map(int, input().split())) price = list(map(int, input().split())) won = price[0] sum = 0 for i in range(n-1): if won > price[i]: # 더 싼 주유소가 나오면 won = price[i]# 가격을 바꿔주자 sum += (won * road[i]) print(sum)