전체 글270 [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. [BOJ] 벽 부수고 이동하기 4 (16946, G2) 벽을 하나 부쉈을 때 그 자리에서 연결된 칸 수는 몇 칸인지 구하는 것이다.생각보다 판이 좀 커질 수 있어서, 그냥 하나하나 다 구하기엔 당연히 TLE 걸릴 것이라 다른 방법이 필요하다.그러면 벽 바로 상/하/좌/우 1칸을 기준으로 빈 연결된 공간의 개수를 더해주면 된다! 하면 틀린다. 빈 공간이 연결되어 있을 수 있다. 뭔 소리냐1111110011101011101111111붉은 1을 잘 보면, 1을 부수면 6칸이 되어야 한다. 하지만 1에 연결되어 있는 상/하/좌/우 만 더하면3 + 3 + 1 + 1 = 8칸으로 맞지 않는다. 무엇이 문제일까?- 연결된 영역을 중복해서 세서는 안된다.- 자기 자신도 포함해야 한다.이 두 가지 문제를 어떻게 해결해야 할까?BFS로 영역을 세는 문제는 많이 풀어보았을 것.. 2024. 11. 20. [BOJ] 가장 오래 걸리는 스도쿠 (G3, 12095) https://www.acmicpc.net/problem/12095 이 문제는 역으로 코드 해석이 필요한 문제이다.해당 코드는 백트래킹으로 풀고 있다. 1부터 차례대로 넣으면서 아니면 거르고 거르고...그렇다면, 맨 앞칸부터 9 8 7 6... 이렇게 오게 만들면 가장 마지막까지 탐색해야 하므로, 이를 강제화 시키면 된다.정확히는 맨 첫 칸에서 삽질하게 만들면 된다. 그리고 그 다음칸도 삽질하게 만들고 만들고...(너무 그러다가 답안이 중복답안이 나오면 망할 수 있으니 욕심내진 말고..)그리고, 이걸 직접 1부터 넣어서 해보게 실패 시키면 깔끔하게 만점. 이렇게 되는 스도쿠 아무거나 하나 던져주면 된다.더, 백트래킹을 어렵게 할 수도 있지만, 이정도만 해도 만점이 너무 충분하다. 3 .. 2024. 11. 19. [BOJ] 치킨 배달 (G5, 15686) - 잃어버린 3시간 https://www.acmicpc.net/problem/15686 다 해놓고 얼탱이 없는 미스로 3시간을 날렸다. dfs 돌릴 때 돌아갈 다음 칸을 잘못 설정하였다... 얼탱이 없는 오타...dfs(pick_num + 1, i + 1) 해야 한다는걸 dfs(pick_num+1, cur_pos+1) 해버림....그 외에는 G5치고는 쉬운 그냥 dfs.잃어버린 나의 3시간....import sysinput = sys.stdin.readlinedef chick_dist(chick_list, house_list): global min_length sum_dist = 0 for cur_h in house_list: cur_min_dist = sys.maxsize for .. 2024. 11. 18. 이전 1 2 3 4 5 ··· 45 다음