ABC 350 D번 복기 - 직접 연결되어있지는 않지만 도달할 수 있는 경로의 개수 구하는법

D - New Friends (atcoder.jp) D - New Friends AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제를 요약하자면... 어떤 노드 X에서 직접적으로 연결되어 있지는 않지만, 다른 노드들을 거쳐서 도달할 수 있는 노드 Z가 존재한다면 그러한 경로의 개수를 구하는 문제 예를 들어 위 그래프에서 1번 노드에서 2,4번은 직접 연결되어 있고, 3번 노드는 직접 연결되어 있지 않은데, 1 > 2 > 3으로 갈 수 있으므로 1개 2번 노드에서 1,3번은 직접 연결되어 있는데 4번은 직접 연결되어 있지..

• format_list_bulleted Atcoder
• · 2024. 4. 21.
• textsms

ABC 348 D번 복기 - 그래프를 재구성하고 BFS/DFS를 해야하는 문제

https://atcoder.jp/contests/abc348/tasks/abc348_d D - Medicines on Grid AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제 자체는 어디서나 많이 보던 기본적인 BFS/DFS 셋팅이다 2차원 맵에 특정 위치에 약이 있는데, 이 약을 먹으면 에너지가 E로 된다. 이동할때마다 에너지가 1씩 감소한다 약은 먹어도 되고 먹지 않아도 되는데, 단 1번만 먹을 수 있고 먹으면 사라진다 에너지 0부터 시작한다고 할때, 목표로 하는 지점에 도착할 수 있는가? 그냥 기본적인 BFS..

• format_list_bulleted Atcoder
• · 2024. 4. 10.
• textsms

ABC 336 C번 복기 - 0,2,4,6,8로만 만든 숫자들 중 n번째 숫자를 찾는 놀라운 방법

C - Even Digits (atcoder.jp) C - Even Digits AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 0,2,4,6,8로만 이루어진 모든 10진수 정수들을 오름차순으로 나열할 때, N번째 숫자를 구하는 문제 N이 $10^{12}$까지니 다 해보면 당연히 시간 초과일거고 최초 몇가지를 한번 나열해보면? 0 0 2 1 4 2 6 3 8 4 20 10(5) 22 11(5+1 = 6) 24 12(5+2 = 7) 26 13(5+3 = 8) 28 14(5+4 = 9) 0,2,4,6,8,20,22,24,26..

• format_list_bulleted Atcoder
• · 2024. 1. 21.
• textsms

ABC 337 D번 복기 - 2차원 배열에서 행,열로 연속한 O의 개수를 빠르게 세는 방법(sliding window + prefix sum)

D - Cheating Gomoku Narabe (atcoder.jp) D - Cheating Gomoku Narabe AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp . o x로 이루어진 2차원 배열에서 .을 o로 바꿀 수 있다. 이 때 행이나 열로 연속한 o의 개수가 k개가 되도록 최소로 바꾸는 횟수 처음에 DFS로 o의 좌표에서 시작해서 .을 o로 바꿔서 해보다가 당연히 시간초과났고 그러다가 행이나 열 각각에서 모두 조사해보면 된다는 생각이 들었다 여기까지는 좋았음 행 한줄에서 어떻게 .을 o로 바꿔야 연속한 o의 ..

• format_list_bulleted Atcoder
• · 2024. 1. 21.
• textsms

ABC 334 복기 - 배열에서 원소 하나를 제거해서 두 원소 절댓값 차이의 합을 최소로 만들기(prefix sum, suffix sum)

1. 문제 C - Socks 2 (atcoder.jp) C - Socks 2 AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 N쌍의 양말이 있는데, 이 중 지정된 K개의 양말은 각각 1개를 잃어버린 상태이다. 양말의 색을 1,2,3,...,N으로 표시할때, 현재 상태에서 적절하게 짝을 짓는다. 짝지은 양말이 i번째 색, j번째 색일때 |i-j| 의 value를 가진다. 모든 짝의 value합이 최소가 되도록 만든다면? 양말의 개수 2N-K가 짝수라면 상관없지만 홀수라면 1개를 제외하고 짝을 지어야한다. 직관적으..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 1. 1.
• textsms

ABC 333 D번 복기 - 리프 노드부터 특정 노드까지 최소로 지우는 법

1. 문제 D - Erase Leaves (atcoder.jp) D - Erase Leaves AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 리프 노드부터 차례대로 지울 수 있을때, 1번 노드를 지우기 위해서 최소로 지워야하는 노드의 개수는 몇개인가? 평소에 골드3정도 트리 DP 문제를 연습했더니.. 해법이 보이긴 하더라 리프 노드라는 것은 자식이 없는 노드인데, 목표로 하는 노드가 1번 노드니까, 1번 노드를 루트라고 생각한다면.. 다음과 같은 트리는 다음과 같이 바꿀 수 있는데, 이런 경우에 리프 노드부터..

• format_list_bulleted Atcoder
• · 2023. 12. 17.
• textsms