본문 바로가기

Algorithm475

[파이썬] 백준 26086: 어려운 스케줄링 (골드3) [파이썬] 백준 26086: 어려운 스케줄링 (골드3) 26086번: 어려운 스케줄링 첫째 줄에 업무의 고유번호의 범위 제한 $N$과 명령 횟수 $Q$, $k$가 주어진다. ($1\leq N,Q \leq 100\,000,\ 1\leq k \leq$ '0번 명령의 등장 횟수') 둘째 줄부터 $Q$개 줄에 걸쳐 명령에 대한 정보가 주어진다. www.acmicpc.net 문제 풀이 0. 방향성 생각 입력을 cmds에 넣는다. 입력을 넣으면서 마지막으로 S가 등장한 위치를 찾는다. 마지막 S가 나오면 그 앞에 값들은 모두 정렬되므로 앞에 입력들은 상관없다. 마지막 S 이후 reverse 상태에 따라 덱의 앞, 뒤에 입력을 넣는다. 1. 입력 from collections import deque import sy.. 2023. 8. 23.
[파이썬] 백준 2096: 내려가기 (골드5) [파이썬] 백준 2096: 내려가기 (골드5) 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 풀이 0. 방향성 생각 메모리가 4MB이다. 3*N 리스트를 작성하지 않고 현재 최대값, 최소값만 기억한다. 1. 입력 import sys input = lambda : sys.stdin.readline().rstrip() n = int(input()) arr_max,arr_min = [0]*3,[0]*3 temp_max,temp_min = [0]*3,[0]*3 for문을 돌면서 현재 arr_max, arr_min을 업데이트.. 2023. 8. 22.
[파이썬] 백준 3687: 성냥개비 (골드2) [파이썬] 백준 3687: 성냥개비 (골드2) 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 문제 풀이 0. 방향성 생각 최대값은 가장 적은 수를 사용해서 앞에 붙여서 가장 큰 자리수로 만들어준다. 최소값은 DP를 사용해서 자연수 n = k + (n-k)로 분리한다. 1. 입력 import sys input = lambda : sys.stdin.readline().rstrip() use = [int(input()) for _ in range(int(input()))] dp = [0]*101 dp[:10] = [0,.. 2023. 8. 22.
[파이썬] 프로그래머스 : 경주로 건설 (Lv.3) [파이썬] 프로그래머스 : 경주로 건설 (Lv.3) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 0.방향성 생각 BFS로 목적지까지 탐색하기. 큐에 현재 (x,y,direction,line,conner) 이런식으로 추가해서 현재까지 cost 계산할 수 있게 한다. 재방문을 해서 최소값이 갱신되는 경우가 있다. 이 경우에는 큐에 또 추가한다. 여기서 주의할 점은 현재 값이 최소로 갱신되더라도 들어오는 방향에 따라서 이후에 값이 달라질 수 있다. 따라서 +500으로 후에 코너에서 추가되는 문제를 제거 밑에 다익풀이도 있음 1. 입력 from colle.. 2023. 8. 22.

티스토리툴바