알고리즘/백준 (9) 썸네일형 리스트형 [백준] K-지폐 28131 https://www.acmicpc.net/problem/28131 28131번: K-지폐 첫째 줄에 $N$, $M$, $K$가 주어진다. $(2\leq N\leq 10\,000; 1\leq M\leq \min\left(100\,000, N(N-1)\right); 1\leq K\leq 50)$ 둘째 줄에 $S$와 $T$가 공백으로 구분되어 주어진다. $(1\leq S,T\leq N;S\neq T)$ 셋째 줄부터 $M$개의 www.acmicpc.net 도로 포장 문제와 마찬가지로 특정 도시에서 특정 도시로 이동하는 최단 이용로를 구해야 하기 때문에 다익스트라를 생각해야 한다. 이용료가 K배수인 이용료를 구해야 하는데 K=1일때를 예시로 들어보자 K = 1일때는 기본 다익스트라와 다를게 없다. 그러면 K=2.. [백준] 1162 도로포장 https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 1번에서 N번까지 가능 경우의 수를 구하라 => 다익스트라 하지만, K개의 도로를 포장할 수가 있습니다. 각 노드에서 도로를 포장해서 갈지 아니면 그냥 갈지 2가지의 경우가 존재합니다. 2가지의 모든 경우를 dis[n][k]에 다 담을 수 있고 dis[n][k]가 작아질때만 q에 추가해 역으로 다시 돌아갈 일이 존재하지 않기때문에 DP를 적용시킬 수 있습니다. .. [ BOJ 백준 1219 오민식의 고민] 오민식오랜만에 글쓰네요. 핑계를 대자면 꾸준히 문제는 풀었지만 블로그 쓰는건 귀찮았어요 데헷 이 문제는 벨만 포드를 대충 공부하고 문제 푸는 (나 같은 무지성 닝겐) 사람에게 혼쭐을 내주는 문제에요. 아마도 이 문제를 검색해서 오시는 분들은 대부분 저와 같이 혼쭐을 받았을 겁니다. (아니면 long long으로 안 풀었던가) 제가 처음에 혼난 이유는 양수 싸이클이 있으면 Gee를 출력했기 때문이에오. 여기서 틀린 이유는 양수 싸이클이 있어도 양수 싸이클을 지나면서 도착점에 도착할 수 없는 경우가 있을 수 있습니다. 3 0 2 4 0 1 9999 1 2 9999 1 1 9999 0 2 0 10000 10000 10000 답: Gee 여기서 저는 "그러면 벨만 포드에서 양수 싸이클을 판단하는 if문의 조건을.. 백준 16500번 문자열 판별 #include #include using namespace std; string A[100]; int dp[101]; int main(void) { string S; cin >> S; int N; cin >> N; for (int i = 0; i > A[i]; dp[0] = 1; for (int pos = 0; pos < S.size(); pos++) { if (dp[pos] == 0)continue; for (int j = 0; j < N; j++) { if (S.find(A[j], pos) == pos) { dp[pos + A[j].size()] = 1; } } } cout [ BOJ 백준 2104번 - 부분배열 고르기 ] www.acmicpc.net/problem/2104 2104번: 부분배열 고르기 크기가 N(1≤N≤100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1≤i≤j≤N)에 대한 점수는, (A[i]+…+A[j])×Min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에다가 i부터 j까지의 최솟값을 곱한 것이 www.acmicpc.net 부분배열 고르기 문제는 1725 히스토그램 문제와 상당히 비슷하니 둘 다 풀어보고 아래 어떤 블로그에서 잘 정리해 놨으니 참고하면 도움이 될 것이다. lookbackonlife.tistory.com/15 [ BOJ 백준 1725번: 히스토그램 ] www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1.. [ BOJ 백준 1725번: 히스토그램 ] www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 모르고 풀면 너무 어렵지만 알고 나면 그렇게 어렵지는 않은 문제였다. 이 문제는 푸는 방법이 2가지 있다! 무려!! 첫 번째는, 분할정복이다 분할정복하는 방법은 바로 사각형들을 좌우로 나누는거다! 응? 사각형들을 왼쪽과 오른쪽으로 나눠서 그 중에서 가장 큰 사각형을 찾으면 되는데! 이건 기존에 방식과 같고 이 방법으로는 이 문제를 풀수 없다. 왜냐면, 좌우로 나눌때 왼쪽 부분의 오른.. [ BOJ 백준 2339번 - 석판 자르기 ] 처음 봤을때 감이 1도 안 잡혀서 다른 블로그를 참고하면서 풀었다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; struct info{ int x, y; }; int N; vector v; vector bul; info check(info s, info e){//석판의 좌상좌표 ~ 우하좌표까지 범위 입력하면 {불순물,결정체}수 출력해주는 함수 int bulsoonmul = 0; int gurjungchae = 0; for (int i = s.x; i N; for (int i = 0; i < N; i++){ vector t; for (in.. [ BOJ 백준 15748번: Rest Stops ] 첫 생각, 산의 오른쪽부터 왼쪽으로 순회하면서 값이 더 커지는 것들을 벡터에 푸쉬했다. 그리고 그 벡터를 reverse취하고 풀었는데! 이런 문제는 마지막꺼를 포함하냐 안하냐 때문에 매우 헷갈리고 실수도 많아진다. 더 좋은 생각, 일단 다 벡터에 넣어 혼란을 방지하고 정렬 알고리즘을 잘 쓰고 visit 배열을 작성하는게 더 좋을듯하다. www.acmicpc.net/problem/15748 15748번: Rest Stops The first line of input contains four integers: $L$, $N$, $r_F$, and $r_B$. The next $N$ lines describe the rest stops. For each $i$ between $1$ and $N$, the $i.. 이전 1 2 다음
