Algorithms/백준 (BOJ)

[백준] 1520번 내리막 길 (Python)

1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 문제 설명 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목..

[백준] 7576번 토마토 (Python)

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 설명 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는..

[백준] 2002번 추월 (Python)

2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net solved.ac 기준 실버 I 난이도 문제이다 예제 입력 1 기준으로 생각한다면 다음과 같다: 입구 출구 ZG431SN ZG206A ZG5080K ZG431SN ST123D ZG5080K ZG206A ST123D 입구에서 제일 마지막에 있던 ZG206A 차량이 출구에서 맨 앞에 있으므로 반드시 추월을 했다 즉, 입구와 출구의 차량을 순서대로 비교하며 같은 순서에 나오지 않았다면 해당 순서에 삽입해준다 코드로 구현하면 아래와 같다: n = int..

[백준] 14501번 퇴사 (Python)

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 풀이 참고로 해당 문제는 삼성 SW 역량 테스트 기출문제로 분류되어 있고 solved.ac기준 실버 III 난이도다 예제 입력1을 기준으로 천천히 생각해보자 첫째 날에 상담을 할 수도 안 할 수도 있다 상담을 한다면: 10만큼의 금액을 벌고 3일 뒤에 다시 상담 여부를 결정한다 반대로, 상담을 안 한다면: 0의 금액을 벌고 그다음 날에 상담 여부를 결정한다 이런 식으로 N만큼의 날짜가 흐를 동안 벌 수 있는 금액 중 최댓값을 구하면 된다 위 로직에 따라 DFS를 활용하면 문제를 해결할 수 있다 import sys sys.setrecursionlimit(10**6) n = int(sys.stdin..