Algorithm/백준

문제링크 : https://www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 누적합 문제였습니다. 신경쓸 부분이 참 많았습니다. 1. Ball 클래스(인덱스, 색깔, 크기)를 만들기 2. ArrayList를 만들어 Ball 정보들을 저장. 3. 크기를 기준으로 오름차순 정렬. 문제풀이 초기 설정을 위와 같이 잡고 문제를 풀었습니다. 문제를 보면 크기가 작고, 색이 다른 공만 잡을 수 있습니다. 예제를 보기 쉽게 나타내보면 다음과 같..

문제링크 : https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 이해가 안되서 이것저것 찾아보며 간신히 이해한 문제입니다. 1. 석순(아래), 종유석(위) 두개로 나누어서 배열 만들기 2. 높이별로 카운트를 높여서 누적합 구하기 3. 누적합 한 배열은 인덱스에서 벽을 몇개 부셔야하는지 나타냄 문제풀이 초기 설정을 위와 같이 잡고 문제를 풀었습니다. 석순 = down, 종유석 = up 배열입니다. up 배열은 인덱스가 반대입니다. 그림으로 설명드리겠습니..

문제 링크 : https://www.acmicpc.net/problem/15683 백트래킹 문제였습니다. CCTV 클래스를 만들기. CCTV는 위치정보와 CCTV타입을 가지고 있음. cctvList를 만들어 CCTV들을 저장 경우의 수를 모두 구해 사각지대 최솟값 도출 문제풀이 초기 설정을 위와 같이 잡고 문제를 풀었습니다. 코드가 상당히 길게 나왔는데 문제의 핵심은 dfs메서드의 이 부분입니다. CCTV now = cctvList.get(depth); // cctv의 타입에 따라 switch (now.type) { case 1: // dir은 방향, 1번 유형은 4개의 경우의 수 for (int dir = 0; dir < 4; dir++) { // map의 정보를 copy에 복사해놓고 copy(map,..

문제 링크 : https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 골드 문제 치고 간단한 BFS 문제였습니다. 1. R, G, B로 나누어져 있을때의 덩어리 갯수(cnt)를 구하기 2. G -> R로 변경하여 R과 B로 나누어졌을때 덩어리갯수(cntRG) 구하기 문제풀이 초기 설정을 위와 같이 잡고 문제를 풀었습니다. 핵심이 되는 bfs는 초기 시작점인 Point p와 bfs중 방문하는 nr, nc의 map 값이 같을때만 진행하도록 하였습니..