Algorithm (41) 썸네일형 리스트형 [Java]BOJ17298_오큰수 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 수열 A의 크기가 백만이므로 N²으로는 시간초과가 난다. 따라서 O(N)으로 해결할 방법을 생각해야한다. 자신을 기준으로 오른쪽 수를 봐야할 경우 보통 뒤에서 시작하는 것이 좋을 때가 많다. 이 문제의 핵심은 오른쪽에서 자신보다 큰 수만 남겨놓는 것이다. 만약 9 5 2 7 순으로 수열이 있다면 5라는 숫자를 볼 때 2와 7을 보는데 7은 남기고 2는 버리는 것이다. 왜냐하면 5 다음의 9를 볼 때를 생각해보면.. [Java] BOJ17136_색종이 붙이기 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 브루트포스로 모든 경우를 따져봐야 한다. 이때 각 종류의 색종이가 5개씩 있으므로 색종이를 놓는 도중에 5개 초과로 사용하는 색종이가 있을 경우 가지치기를 통해 경우의 수를 줄일 수 있다. 이 함수가 바로 check함수이다. 처음에 1의 갯수(cnt)를 센 후 색종이를 덮는 함수를 돌려 이 cnt가 0이 됐을 경우 사용한 색종이의 수를 센다. setpaper함수를 이용하여 색종이를 덮는 .. [Java] BOJ1700_멀티탭 스케줄링 www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 꽂혀있는 플러그 중 처음으로 사용되는 시점이 가장 나중인 것을 교체하는 방법으로 그리디 접근을 하였다. count 배열은 각 장치별 남은 사용 횟수를 담고 있다. 콘센트를 탐색하여 이미 장치의 플러그가 꽂혀있는지와 빈자리가 있는지 판단한다. 현재 꽂으려는 장치(cur)가 이미 꽂혀있다면 패스하였고 꽂혀있지 않고 콘센트에 빈자리가 있다면 해당 콘센트에 장치를 꽂아준다. 모든 콘센트에 플러그가 꽂혀있고 현재 장치가.. [Java] BOJ1697_숨바꼭질 www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 동생의 위치는 고정되어 있고 수빈이는 1초에 뒤쪽으로 한 칸씩만 갈 수 있으므로 N >= K 일 때 결과는 N-K이다. 그 외 경우에는 BFS를 통해 탐색을 해야한다. 현재 위치를 n이라 할 때 n-1, n+1, n * 2의 위치에 대해 경곗값 체크와 방문 체크를 통해 Queue에 추가해야 한다. 이때 이동시간인 cnt를 같이 담고 다닌다. n == K일때 가장 최소 시간으로 동생을 .. [Java] BOJ16926_배열 돌리기 1 www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 단순 구현 문제이다. 방향벡터(dn, dm)를 순차적으로 잘 정의해놓는 것과 배열의 범위를 신경 써서 구현해야 한다. 또한 시작점을 정할 때 N과 M중 더 작은 것에 범위가 맞춰진다. import java.io.*; import java.util.StringTokenizer; public class Main { sta.. [Java] BOJ16918_봄버맨 www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net "다음 1초 동안 봄버맨은 아무것도 하지 않는다." 이 규칙을 통해 N == 1일 때는 처음과 상태가 같다는 것을 알 수 있다. "다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다." 이 규칙에서 2초에 모든 칸에 폭탄이 설치되는 것을 알 수 있고, 이것이 2초마다 반복 되는 것을 알 수 있다. 따라서 N이 짝수일 때는 모든 .. [Java] BOJ1660_캡틴 이다솜 www.acmicpc.net/problem/1660 1660번: 캡틴 이다솜 캡틴 이다솜은 자신의 해적선에 적을 공격하기 위한 대포알을 많이 보관해 놓는다. 다솜이는 미적감각이 뛰어나기 때문에, 대포알은 반드시 사면체 모양으로 쌓아놓아야 한다고 생각한다. 사면 www.acmicpc.net dp1에는 층마다의 대포수가 담겨있고 이 dp1을 이용하여 사면체의 대포수를 담은 배열이 dp2이다. 이 dp2를 이용해 결과 배열을 만들었다. 예를 들어 5개의 대포알을 가지고 있다고 할 때 4개의 대포알로 만들 수 있는 경우의 수에 1개의 대포알로 만들 수 있는 경우 1을 더한 값과, 1개의 대포알로 만들 수 있는 경우의 수에 4개의 대포알로 만들 수 있는 경우 1을 더한 값의 최솟값이 res [5]에 세팅된다. i.. [Java] BOJ16234_인구 이동 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net BFS를 돌아 두 나라의 인구 차이가 L 이상 R이하일 때 같은 tag을 부여하였다. tag값이 곧 연합을 의미한다. tag를 부여할 때 tag의 수 tagCnt와 그 태그의 인구수 tagSum을 구하는데 BFS를 다 돌고 나서 tag 1(연합 1)의 tagCnt가 0이라면 어떠한 연합도 생기지 않은 것이므로 반복문을 빠져나온다. 그 경우가 아니라면 각 연합에 속해있는 나라들에 tagSum / t.. 이전 1 2 3 4 ··· 6 다음