Dalin's Archive

나는 특히 분할 정복이 어렵다..ㅠ 많이 풀어보지 않아서 그런 것 같다... 그래서 🥈실버🥈 분할 정복 문제를 몇 개 풀어봤다. 2630. 색종이 만들기 문제 보러 가기! 정사각형 형태로 종이가 주어진다. 칸마다 파랑일 수도 있고, 하양일 수도 있다. 주어진 범위의 모든 칸이 같은 색깔이면 그만 자른다. 색이 섞여 있으면 4등분을 한다. (세로로 반, 가로로 반. 정사각형 모양으로) 파란 색 종이 개수를 저장하는 blue_cnt, 하얀 색 종이 개수를 저장하는 white_cnt를 0으로 초기화한다. divide_and_conquer함수에 시작하는 인덱스와 끝나는 인덱스, 한 변의 길이를 넣는다. divide_and_conquer 함수 주어진 범위를 쭉~ 보면서(check 함수) 다 같은 색깔이면 하양인지..

https://www.acmicpc.net/problem/13422 풀이 🐸 N개 집이 원형으로 쭉~ 놓여있고 각각 집에는 돈이 있다. 도둑은 연속된 집 M개를 턴다.(각 집에 있는 돈을 다 가져간다) 이 돈이 K 미만이어야만, 도둑이 안전하게 돌아갈 수 있다. 도둑이 무사히 돌아갈 수 있으면서, M개 집에서 도둑질할 때 그 경우의 수를 구해야 한다. 투 포인터로 쭉~ 봐줬다. 도둑질 당하기를 시작하는 집, 끝나는 집을 left, right로 뒀다. 그 집들에서 훔친 돈을 stolen_money로 뒀다. 맨 처음에는 left부터 right까지의 집에 있는 돈을 다 더해서 stolen_money를 초기화했다. 그 후에 한 집씩 옮기면서 stolen_money를 봤다. 한 집씩 옮길 때 left집의 돈을 s..

문제 보러 가기! 풀이 🎊 모든 강연 요청을 (요금, 일자) 형식의 tuple로 이뤄진 리스트에 저장했다. 일자 -> 요금이 큰 순서대로 정렬했다. d일 안에 강연을 해야 한다는 것에 대해 생각해보자. d가 7이라면, 1일 안에 강연해도 되고 2일 안에 해도 되고 3일 안에 해도 되고 .... 7일 안에 강연해도 된다는 뜻이다. 만약 d가 1이라면 1일 안에 강연해야만 돈을 준다는 뜻이다. => 일자가 큰 순서대로 봐준다!! 일자가 큰 순서대로, 그 일자에 가능한 강연의 비용을 우선순위 큐에 넣는다. (같은 d로 요청한 강연이 여러 개라면 모두 넣는다) 그 후 각 일자마다 보면서, 그 일자에 강연을 한다고 했을 때 돈을 가장 많이 주는 강연을 한다. (우선순위 큐에서 heappop) 주의점 👻 heapq..

문제 보러가기! 풀이 🌷 지문이 웹툰 내용 같고 재미있었다 ㅋㅋ 핵심은 슬라임 에너지가 적은 슬라임을 두 개씩 합성하는 것이다!! 그걸 파악한 후에는 카드 정렬하기 문제와 비슷하게 풀었다. 카드 정렬하기 문제에서는 더하기라면, 이 문제에서는 곱하기라는 점 정도만 다른 것 같다. 아래와 같이 풀었다. 처음 슬라임을 리스트로 받은 후에 heapify하기 청구될 전기 에너지 초기값은 1로 시작하기(곱의 항등원은 1이므로) 힙의 길이가 2 이상일 동안은(즉, 슬라임이 두 개 이상일 때) 힙에서 슬라임 에너지가 적은 슬라임을 두 개 꺼낸다. 각각 슬라임 에너지가 A, B 라고 하자. 그 둘을 곱하면 슬라임 에너지가 AXB인 슬라임이 되고, 그걸 힙에 넣는다. 또 청구될 전기 에너지에 A X B한 값을 곱한다. 힙..

문제 보러 가기! 오랜만에 BFS를 풀어서 재미있었다~! 평범한 BFS 문제 + 빙판 부분이 특별했다. 먼저 늑대의 위치를 확인해서 리스트에 넣은 후에, 늑대 한 마리씩 확인했다. (늑대가 여럿 있을 수도 있음) 늑대가 방문할 수 있는 곳인지 방문 체크를 했다. (wolve_can_go 2차원 리스트) 빙판 부분은 while을 이용해서, 쭉~ 미끄러지듯 가줬다. 가고 있는 방향 쪽으로 한 칸 더 갔을 때(범위 확인 후) 빙판이면 한 번 더 가기 초원이라면 그만!(즉 늑대가 방문할 수 있다고 체크한 후, 큐에 넣었다.) 산이라면 그 이전 위치에서 멈추도록 했다. (멈춰서 다른 방향 갈 수 있기 때문이다! 처음에 이 부분을 안 처리해서 틀렸다. 그 이전 위치를 방문 체크한 후, 큐에 그 이전 위치를 넣았다...

문제 풀러 가기! 꼼꼼히 천천히 구현했다~ 사 방향을 일일이 코드로 짜서 좀 긴데ㅠ, 줄일 수 있을 것 같기도 하다. 🧐 헷갈렸던 부분 이미 넘어진 격자의 도미노를 공격수가 무너뜨리려고 할 때는 공격수 점수를 카운트 하면 안된다! x, y, d 는 map(int,input().split())으로 하면 안되는데 해서, 잠깐 에러를 만났다.. d는 숫자가 아니고 알파벳이다.. 다시 도미노를 쌓을 때는, 원래 가지고 있던 높이 만큼 쌓아줘야 하므로 그 높이를 origin_height에 copy.deepcopy를 이용해서 저장해뒀다. 👩‍💻 코드 import sys, collections, copy input = sys.stdin.readline N, M, R = map(int, input().split()) ..

문제!! 풀이 🌷 통나무의 세로로 입력으로 들어오지만 가로만 봐주면 된다. 선 긋는 스위핑 문제처럼 풀면 되는 것이었다. 그 문제 포스팅은 여기..ㅎㅎ 어려웠던 점 🦄 처음에는 통나무의 가로, 세로 좌표 둘 다 봐줘야 하는 줄 알았다.. 좌표는 10^9까지 있다고 하는데, 가로 세로를 고려해서 2차원으로 만들면 너무 클 것 같은데... ㅠ 어떻게 하나 고민했다. 그런데 가로!!!만 봐주면 되는 것이었다. 점프하면 되니까 세로는 볼 필요가 없었다. 원래 입력 받은 리스트를 정렬해서, 그 순서가 망가진다.. 그러니까 원래 인덱스를 가지고 있어야 한다! 그래야 어떤 통나무랑 다른 통나무랑 이어져있는지 체크가 가능하니까!!! 코드 🐸 import sys input = sys.stdin.readline N, Q ..

문제 보러 가기! TMI 내 기억 상 처음으로 푸는 영어 문제이다. 풀이 🦄 문제 이해를 돕기 위한 설명용 그림..ㅎㅎ 처음에 1번 섬에서 무조건 시작하고, 그 병력을 가지고 시작한다. 지배한 섬과 이어진 섬은 공격 후보가 된다. 이어진 섬의 병력이 우리(spanning nation) 병력보다 적을 때만!! 그 섬을 지배한다. 우선순위 큐를 활용하면 된다. 우선순위 큐, q에 공격할 수 있는 후보들(섬)을 집어 넣었다. 인접 리스트로 섬들의 연결 관계를 저장한다. 각 섬의 병력을 island_army 리스트에 저장한다. 각 섬을 공격할 수 있는 후보(q)에 넣었는지 여부를 저장하는 visited 리스트를 만든다. 1번 섬에서 시작한다. 우리 병력(spanning_army_cnt)를 1번 섬의 병력으로 업..

문제 보러 가기! 내 근황 (TMI..) 꺄~ 싸피 공통 PJT를 잘 마무리하고 돌아왔다 ~~!! 마지막 열흘 정도는 PJT에 집중하느라고 PS를 못하다가 오랜만에 문제를 풀었다 !! 내가 좋아하는 heapq를 이용하면 되는 문제였다. 설명 카드 묶음 여러 개가 있는데, 두 묶음씩 골라서 합쳐나간다. 합칠 때는 그 두 묶음의 개수만큼 비교를 해야 한다. 최소 몇 번의 비교가 필요한가? -> 적은 것부터 합치는 게 좋다 !!라는 걸 파악하고 heapq를 사용하면 됐다. 비교 개수를 담을 변수인 cnt를 0으로 초기화하고 시작했다. q에 숫자 카드 묶음 각각의 크기를 넣었다. heapify를 이용해서 q를 우선순위 큐로 만들어줬다. 그리고 q의 크기가 1이 될 때까지, 가장 적은 것 두 개씩을 더해서 다시 ..

문제 보러 가기! 간단 소감 오랜만에 dfs 문제를 풀어서 재밌었다 ㅎㅎ 그리고 visited 아이디어를 생각하는 것도 특이하고 재밌었다~~ 문제 설명 로봇이 4방향(동서남북) 중 한 방향으로 N번 이동한다. 각 방향으로 이동할 확률을 준다. 같은 곳을 또 방문하면 이동 경로가 단순하지 않다고 한다. 로봇의 이동 경로가 단순할 확률을 구하는 문제였다. 풀이 로봇이 4방향으로 N번 이동하고, N이 14보다 작다고 해서 딱 순열! 이 생각났다. DFS로 각 방향을 가봤다. dfs를 할 때 가지고 다니는 변수는 지금까지 몇 번 이동했는지, 현재 인덱스, 현재 위치까지 이동할 확률. 그런데 로봇이 단순하지 않은 경로로 이동할 경우, 더이상 볼 필요 없이 리턴해주면 되니까 백트래킹이라고도 할 수 있겠다. visi..