본문 바로가기

전체 글107

[구현] 백준 17143 : 낚시왕 - 파이썬 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 생각하기 상어의 정보 저장? 리스트에 각 상어의 r, c, s, d, z(위치, 크기, 방향, 속도)를 저장 shark[r][c] 는 (r,c)에 있는 상어 -> 상어의 위치가 변하고 위치가 중요하기 때문에 현재 문제에는 이러한 접근이 구현하기 편함 상어의 같은 위치에 여러마리 모든 상어를 이동 시키고 모든 칸을 살펴 보면서 2마리 이상이면 한마리로 -> 배열이 여러차원으로 형.. 2022. 2. 14.
[구현] 백준 16235 : 나무 재테크 - 파이썬 Python https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 생각하기 각 칸에 나무가 있고 봄, 여름, 가을, 겨울에 따라 각 칸에 대한 이벤트를 수행 시간복잡도 최대 1000년이므로 1000년동안 N*N의 칸을 돌아다닐 예정 N의 최대는 10이므로 100개의 칸을 돌아다닌다 각 칸에서는 최대 100개의 나무가 있을수 있다 1000 * 100 * 100 < 10^9이므로 충분히 시간 복잡도 안에 해결 가능 N, M, K = map(int, .. 2022. 2. 8.
[BFS] 백준 5014번 : 스타트링크 - 파이썬 Python https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 생각하기 버튼을 누르는 최소 횟수를 구하는 것이기 때문에 전형적인 BFS 문제라고 생각하였다 시간 복잡도 S, G, F가 모두 1000000 이하의 수이므로 충분히 BFS로 풀어도 시간 안에 들어올 수 있는 문제 구현하기 q = deque() (현재 강호가 있는 층, 현재까지 누른 버튼의 횟수) 를 q에 append / popleft 한다 올라가는 버튼 현재 강호가 있는 층 + U 가 건물을 넘지 않아야 함 .. 2022. 2. 7.
[BFS] 백준 14395 : 4연산 - 파이썬 Python https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 생각하기 최소의 변환을 찾으면 되는 문제이기 때문에 BFS로 접근해야겠다고 생각 평소처럼 visited 배열(list)을 통해서 방문 여부를 검사려고하니, 메모리 문제가 발생 -> 각 연산의 특성을 잘 생각해보면 모든 10^9숫자를 다 사용하지는 않음 뺄셈을 만나면 S - S 로 0이 되므로 사실상 끝 나눗셈을 만나면 S / S 로 1이 되므로 사실상 2의 배수가 된다 S^a * 2^b 형.. 2022. 2. 7.

티스토리툴바