분류 전체보기156 백준 4435 중간계 전쟁 1일 1블로그 https://www.acmicpc.net/problem/4435 4435번: 중간계 전쟁 첫째 줄에 전투의 개수 T가 주어진다. 각 전투는 두 줄로 이루어져 있다. 첫째 줄에 간달프 군대에 참여한 종족의 수가 주어진다. 이 값은 공백으로 구분되어 있으며, 호빗, 인간, 엘프, 드워프, www.acmicpc.net 풀이 문제에서 제시된 조건에 맞추어 weighted sum을 구해 비교해주면 되는 문제이다 시간 복잡도 : O(T) 감상 : 오늘의 아티스틱 스위밍 대회 즐거웠다. /* basic setup {{{ */ #include #define ff first #define ss second #define pb push_back #define sz(x) ((int)x.size()) #d.. 2022. 11. 26. 백준 2493 탑 내일 아티스틱 스위밍 대회한다. 많이 기대된다. https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 stack을 사용해 해결해줄 수 있는 문제이다. 특정 위치에 있어서 해당 위치 이전에 있는 탑들이 현재 위치에 있는 탑들보다 작을 경우 이후의 탑들에서 해당 작은 탑들에 도달할 수 있는 방법은 없다. 이 원리를 이용해 한번 탐색해준 탑은 사용하거나 제거해줄 수 있는 것이다. (시간 복잡도 O(N)) 감상 이제 이런 문제들은 쉽게 풀린다. .. 2022. 11. 25. 백준 7595 Triangles 큐빙 맞왜틀.. 이건 말이 안된다 반례를 찾았는데도 모르겠다. https://www.acmicpc.net/problem/7595 7595번: Triangles Each line of input contains a single positive integer, n, 1 n){ if(n==0) break; FOR(i,0,n){ FOR(j,0,i+1) cout 2022. 11. 24. 백준 17267 상남자 0-1 bfs 응용문제? https://www.acmicpc.net/problem/17267 17267번: 상남자 CTP의 대표 상남자 영조는 자유롭게 이동하는 것을 좋아한다. 그렇지만 영조는 상남자이기 때문에 위아래로만 간다. 따라서 위, 아래로는 얼마든지 이동할 수 있지만 왼쪽, 오른쪽으로는 이동하 www.acmicpc.net 풀이 그래프를 탐색하며 상하로 이동하는 것의 비용은 0이고 좌우로 이동하는 것의 비용은 1이다. 단순 bfs에 push_front 를 추가한다고 생각하면 된다. 비용이 0인 이동을 push_front로 이동해 도달할 수 있는 모든 곳을 도달해야한다. 백준 게시판에서 반례를 찾아보고 해결하였다. 상하좌우로 한칸씩 이동할 경우 다음의 케이스에서 (2,3) 지점을 탐색해줄 수 없다... 2022. 11. 23. 백준 16234 인구 이동 플레 5 풀다가 너무 무서워져서 골드 5로 내려왔다. 편안. https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 매번 연결해주고 연결 정보를 vector v로 관리해주고 초기화해주고 하며 교환이 발생하지 않을 때까지 이를 반복해준다. 시간 복잡도 : O(2000∗N2) 감상 : 처음에 많이 해맸다. 일찍이부터 그냥 bfs 써서 했으면 편하게 했을걸 괜히 엄한 방법으로 하려다 시간만 많이 썼다. 아쉽다. /* basic se.. 2022. 11. 22. 이전 1 ··· 15 16 17 18 19 20 21 ··· 32 다음
