본문 바로가기
728x90

알고리즘/[python] 백준 BOJ328

[python] 백준 13335 트럭 https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 문제 해결 다리를 que를 이용하여 해결하면 좋겠다는 생각이 바로 든다. que안에 있는 숫자의 합은 l을 넘어서는 안된다. 1초마다 FIFO로 첫 번째 트럭 or 공기(?)가 나가고 대기중인 트럭이 들어오거나 공기가 들어오는 시물레이션을 코딩하면 된다. 공기가 들어갈지 트럭이 들어갈지의 기준은 다리에 있는 무게의 합+대기중인 트럭의 무게가 l보다 .. 2023. 12. 10.
[python] 백준 1069 집으로 https://www.acmicpc.net/problem/1069 1069번: 집으로 은진이는 지금 (X, Y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 이동할 수 있는 방법은 다음 두 가지이다. 첫 번째 방법은 걷는것이다. 걸을 때는 1초에 1만큼 움직인다. 두 번째 방법 www.acmicpc.net 문제 해결 걸을 때 1초에 1만큼 움직인다. 이는 택시기하학으로 움직이는 것이 아니고 자유롭게 대각선이든 반경 1안에 모든 점으로 1초에 이동할 수 있다는 것이다. 점프도 마찬가지다. 일직선으로 할 수 있다는 뜻은 정확히 거리가 D인 지점까지 T초에 간다는 뜻이다. 따라서 현재 거리, 즉 (x,y)와 (0,0) 거리를 구한다. 현재 거리가 한 번에 뛰어서 갈 수 있는 거리보다 크거나 .. 2023. 12. 7.
[python] 백준 1981 배열에서 이동 https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 문제 해결 (1,1)에서 (n,n)까지 가는데 거쳐간 수들 중 최솟값과 최댓값 차이를 구하는 문제 이동하면서 최솟값과 최댓값을 변경해가며 저장하고 갈 수도 있을 것 같은데 그러면 que안에 너무 많은 데이터가 저장이 되어 메모리 제한에 걸린다. 따라서 최솟값과 최댓값을 고정값으로 가져가며 그 안에 수들이 통과하여 이동할 수 있는지 확인해가는 식으로 bfs를 이용할 수 있다는.. 2023. 12. 4.
[python] 백준 30823 건공문자열 https://www.acmicpc.net/problem/30823 30823번: 건공문자열 양의 정수 $N$, $K$와 영어 알파벳 소문자로 구성된 길이가 $N$인 문자열 $S$가 주어진다. reverse(i)를 $S$의 $i, i+1, ... , i+k-1$번째 문자로 이루어진 부분 문자열을 뒤집는 연산이라고 정의하자. $i = 1, 2, www.acmicpc.net 문제 해결 시간초과에 고민을 많이 해보게 된 문제 하나씩 돌리면 당연히 정답이 나오지만 숫자가 500000까지 가능하므로 시간초과가 난다. 따라서 규칙을 찾아야한다. 규칙은 직접 해보면서 찾는 것이 쉽다. 먼저 K번째 문자부터 끝문자까지 순서대로 나온다는 것을 알 수 있다. 그리고 N과 K의 차이가 홀수면 앞에 K-1번째 문자까지 순서대.. 2023. 12. 3.
728x90