분류 전체보기150 백준 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*N^2)$ 감상 : 처음에 많이 해맸다. 일찍이부터 그냥 bfs 써서 했으면 편하게 했을걸 괜히 엄한 방법으로 하려다 시간만 많이 썼다. 아쉽다. /* basic se.. 2022. 11. 22. 백준 25386 라즈베리 파이 플레 2가 푸는 플레 2 문제.. 뭐가 안 맞습니다. https://www.acmicpc.net/problem/25386 25386번: 라즈베리 파이 한별이는 $3$년 만에 오프라인으로 개최되는 UCPC 본선을 맞아 특별한 이벤트를 계획했다. 바로 참가자들과 라즈베리 파이를 나눠 먹는 것이다! 한별이는 원기둥 모양의 파이를 모든 조각이 밑면 www.acmicpc.net 풀이 라즈베리(토핑)을 최소로 이동해주는 방법을 생각하기 이전에 모든 참가자의 요구를 들어줄 수 없는 경우(-1)를 먼저 생각해야 한다. 토핑은 한 번 합쳐지면 다시 나누어질 수 없기 때문에 모든 참가자들의 요구를 들어줄 수 없는 경우가 발생한다. 모든 참가자의 요구를 들어줄 수 없는 경우는 다음 세 가지로 나뉜다. 1. 서로 다른 두 참.. 2022. 11. 21. 이전 1 ··· 14 15 16 17 18 19 20 ··· 30 다음
