본문 바로가기

알고리즘 & PS69

[BOJ] 파이프 옮기기 1 (17070, G5) 문제 내용  풀이 과정도착 상태가 가로인지, 세로인지, 대각선인지를 나눠서 모두 합쳐주면 된다. 즉, 이를 기억하는 dp를 만들면 된다.위의 7가지 이동 상황을 모두 각각을 점화식으로 만들면 되는데, 몇 가지 주의사항이 있다.1. 맨 첫번째인  0행의 경우 가로줄 이동만 가능하다. 벽을 만나기 전까진 1, 벽을 만난 다음부터는 무조건 02. 두 번째 행부터는 세로, 대각선 이동도 가능하다.  단, 대각선은 0열, 1열에서는 움직일 수 없다. 파이프는 2칸이다.3. 맨 첫번째 열은 그냥 경우가 0이다.이를 바탕으로 최종 마지막 칸에서 가로 + 세로 + 대각선 하면 되는 문제.import sysinput = sys.stdin.readline# 가로로 도착하냐, 세로로 도착하냐, 대각선으로 도착하냐를 나눠서 .. 2024. 11. 24.
[BOJ] 텀 프로젝트 (9466, G3) DFS로 풀 수 있는 문제. 좀 까다로운 문제이다.문제의 핵심은 "사이클"을 찾아 내는 것이다. 하나의 원소를 넣고, 돌면서 방문 여부를 체크하게 된다. 이 때, 이동한 경로를 넣고, 이미 방문했는데, 사이클 리스트에 있다면 사이클이라고 판단, 반환하는 것이다.문제는, 사이클에서 일부 삐져나온 상황이다. (2 4 7 3 4 7 3.... 이렇게 도는 상황) 이를 주의해서 구현한다.import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**6)def dfs(cur_std, cur_result): visited[cur_std] = True cur_cycle.append(cur_std) next_std = std_list[cur_std] .. 2024. 11. 24.
[BOJ] 귤나무 (31005, G1) 이번 문제는 상당히 어려운 문제입니다. 어려운 알고리즘을 쓰진 않지만, 최적화를 잘 해야 합니다.문제 내용 풀이 과정우선 문제를 이해해 봅시다. 순서대로, 귤을 가져갑니다. 못 가져가면 아무것도 못하고 다음 애가 가져갑니다... 반복합니다.아무도 귤을 못 가져가는 순간이 옵니다. 그 대로 저 날짜까지 가면 됩니다. 대략 숫자 범위를 보면, 최악의 케이스여도 대충, 20만 * 10^18 * 10^12 잡아도  10^100보다는 확실히 작습니다. 따라서 10^100은 크게 고려하지 않아도 될 거 같습니다.즉 문제는, 마지막에 몇 개가 남을 것인가? 에 집중하면 됩니다. 이를 역으로 생각해 봅시다.곰곰이들 중, 과일을 가장 적게 원하는 애가 있을 것입니다. 그 애가 원하는 것보다 과일이 더 적게 남는다면? 남.. 2024. 11. 22.
[BOJ] 도서관 (1461, G4) https://www.acmicpc.net/problem/1461  가장 멀리 있는 책은 뒤에 가져가서 놔두고.. 가까운 책은 그냥 왕복 해도 된다.그리고 여러 권 들 수 있으면 가장 가까이 있는 책들은 몰아서 가져가면 된다....네.! 그리디하게 풀면 됩니다.가장 먼저 드는 생각 / sort해서 책에 들 수 있는 개수 만큼씩 나눠 가자.그러면, 그냥 쉽게 최대 거리 계산 찍고, 마지막만 멈추면 끝!!     일까요?       네! 당연히 틀렸습니다!문제가 생기는 지점은 테케로도 제공되는데 바로, 양수 방향과 음수 방향이 섞일 때입니다.양수와 음수가 섞이면 0을 거쳐서 다시 왔다갔다 해야 합니다. 효율적이지 않습니다.여기서 하나 관찰할 수 있는데 양수와 음수가 섞이면 어차피 0에서 책을 덜 들고 출발하.. 2024. 11. 21.
[BOJ] 2048 (Easy) (12100, G1) https://www.acmicpc.net/problem/12100빡구현 문제인데, 골드 1 치고는 정말 쉽다.기본적으로 5번의 명령을 받는 것은 DFS긴 하다.  5번 정도니까, 크게 뭐 할 거 없이 모두 다 시도해보면 된다.문제는 2048을 어떻게 구현할 것이냐인데, 줄별로 뽑아서 만들면 된다.스와이프 하면, 그 방향으로 중력이 적용되어 모든 공백이 없어지고 같은 숫자는 딱 한 번만 더해진다.추가로, 우선순위는 그 방향의 최초 두개 부터다 (예시 - 8 8 8 0 에서 좌측 스와이프는 8 16 0 0 이 아니라 16 8 0 0)이를 구현할 방법은 다음과 같다.1. 모든 0을 다 반대쪽으로 옮겨 준다.2. 맨 앞부터 두개씩 비교하여 같은 숫자면 더 스와이프 방향에 가까운 쪽에 수를 몰아주고, 반대쪽은 .. 2024. 11. 21.
[BOJ] 배 (1092, G5) https://www.acmicpc.net/problem/1092 엄청나게 삽질한 문제...1차 시도 / 가장 무거운 것과, 가장 가벼운 것을 동시에 실어 날라주는 생각을 했지만... 테케부터 걸린다.아마, 중간 무게에서 효율성을 놓친 것으로 보인다.2차 시도 / 가장 무거운걸 실어보내는거로 생각..? 하지만 놀아버리는 크레인이 나오면 안된다.3차 시도 / 현재 크레인이 실을 수 있는 가장 무거운 것을 찾자.단, 현재 크레인이 가망이 없으면 탐색해봤자 라는 걸 걸러내야 효율적이다.!import sysinput = sys.stdin.readlinecrane_num = int(input())crane_list = list(map(int, input().split()))crane_list.sort(revers.. 2024. 11. 21.

티스토리툴바