Baekjoon6 백준 21909 Divisible by 3(Python) 서론오랜만에 백준입니다. 수학을 많이 쓰려면 충분히 많이 쓸 수 있고 결국은 DP를 잘 활용해야 풀리는 문제입니다. 한 번 맛 봅시다. 본론https://www.acmicpc.net/problem/21909 21909번: Divisible by 3For an array $[b_1, b_2, \dots , b_m]$ of integers, let’s define its weight as the sum of pairwise products of its elements, namely as the sum of $b_ib_j$ over $1 \le i www.acmicpc.net 문제 설명어떤 수열이 주어졌을 때 Weight를 정의합니다. Weight는 여기서 sum of pairwise product로 정의됩니.. 2023. 10. 2. 7578번 공장(Fenwick tree, python) https://www.acmicpc.net/problem/7578 들어가는말 오랜만에 쭉 기억하고 싶은 문제가 있어 포스팅하게 되었습니다~ 1년 반 전에 1615번 교차개수세기라는 문제를 풀었었습니다. 그 때 답지를 보지 않고 풀고 싶어서 공부하고 공부하다가 6개월만에 화장실에서 떠오른 번뜩이는 아이디어로 풀었던 기억이 있어요 ㅎㅎ 그 때는 누적합의 아이디어로 풀었었습니다. 한동안 잊고 살다가 이 문제를 발견했네요. 그 문제와 완전히 동일하고 조금 현실의 문제처럼 둔갑을 하고 있을 뿐입니다. 오랜만에 풀어보고자 접근했구요. 성장한 저는 Fenwick Tree로 이 문제를 풀어보았습니다. 서론이 길었네요. 바로 시작해봅시다. 문제 및 입출력 풀이 이 문제는 Bipartite graph의 교차 개수를 세는 .. 2023. 7. 8. 1725번 히스토그램(Python,스택) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 1. 문제 및 입출력 2. 풀이 Well-Known 문제 답게 풀이가 굉장히 다양합니다. 저는 그중에서도 스택을 이용한 풀이를 소개하려고 해요! 문제의 이해는 쉽습니다. 간단히 가장 큰 넓이의 직사각형을 히스토그램 내에서 찾으면 됩니다. 되게 Naive하게 접근해서 $O(n^2)$으로 알고리.. 2023. 6. 5. 1520번 내리막길(dps+dp) HTML 삽입 미리보기할 수 없는 소스 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제정의 입출력 간단한 생각 정리 예전에 확률과 통계에서 점 by 점으로 이동하며 어떤 점에서 도착하는 경우의 수는 주변 점들에서의 경우의 수의 합과 같다는 논리를 사용하고 싶었다. 처음에는 dfs로 접근했는데 당연히 시간초과가 났고(예상했고) 두번째는 dp로 접근했는데 이동하는 경로가 단순하지가 않아서 실패(예상 못함) 그런데 문제 질문에 dfs+dp로 풀라고 .. 2023. 6. 4. 이전 1 2 다음
