import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int count = 1;
int number = 666;
while (count != N) {
number++;
if (String.valueOf(number).contains("666")) {
count++;
}
}
System.out.println(number);
}
}
[알고리즘]
- 부르트 포스
[풀이]
처음엔 생각보다 어려워보여서 실버 5 문제가 맞나? 라고 의심했었다. 알고보니 정말 부르트하게 풀었더니 정답이였다.
import java.io.*;
import java.util.*;
public class Main {
static int R, C, answer = Integer.MAX_VALUE;
static char[][] graph;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static Queue<int[]> jihoon = new LinkedList<>(); // 지훈이의 좌표가 담긴 큐
static Queue<int[]> fire = new LinkedList<>(); // 불의 좌표가 담긴 큐
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
graph = new char[R][C];
for (int i = 0; i < R; i++) {
String input = br.readLine();
for (int j = 0; j < C; j++) {
graph[i][j] = input.charAt(j);
if (graph[i][j] == 'J') {
jihoon.offer(new int[]{i, j});
}
if (graph[i][j] == 'F') {
fire.offer(new int[]{i, j});
}
}
}
br.close();
int answer = 0;
while (true) {
answer++; // while 반복문을 1회 시행할 때 마다 1분이 지난것이므로 1씩 증가
int fireSize = fire.size(); // 불의 좌표가 담긴 큐의 크기 == 불의 갯수
while (fireSize > 0) { // 번져야 할 불의 개수만큼만 반복, 이미 번진 불은 번지는것을 반복하지 않음
fireSize--;
int[] tmp = fire.poll();
int x = tmp[0];
int y = tmp[1];
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
if (graph[nx][ny] == '.' || graph[nx][ny] == 'J') { // 불이 번진 위치가 벽이 아니라면
fire.offer(new int[]{nx, ny}); // 새로운 불의 좌표를 큐에 담는다
graph[nx][ny] = 'F'; // 번진만큼 지도를 갱신
}
}
}
}
int jihoonSize = jihoon.size();
while (jihoonSize > 0) { // 지훈이의 좌표가 담긴 큐가 비어있지 않을 경우
jihoonSize--; // 새로운 지훈이의 좌표갯수만큼만 반복, 이미 이동한 지훈이는 이동하는것을 또 반복하지 않음
int[] tmp = jihoon.poll();
int x = tmp[0];
int y = tmp[1];
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= R || ny < 0 || ny >= C) { // 탈출을 했을 경우
System.out.println(answer);
return;
}
if (graph[nx][ny] == '.') { // 이동가능한 자리일 경우
jihoon.offer(new int[]{nx, ny}); // 이동한 위치의 좌표를 큐에 담는다
graph[nx][ny] = 'J'; // 이동한 위치를 J로 갱신 (사실 이 코드는 필요하지는 않음)
}
}
}
if (jihoon.isEmpty()) { // 새로이동할 때마다 지훈이의 좌표가 담긴 큐 jihoon 이 늘어나는데, 이동이 불가능하면 큐가 비게 됨
System.out.println("IMPOSSIBLE");
return;
}
}
}
}
[설명]
bfs심화문제이다. 지훈이가 4방탐색을 하며 지도밖을 나갈 경우 반복문이 종료되는 것까지를 구현하는것은 약간만 생각하면 할 수 있다. 하지만 다른문제와 다른것은 지훈이가 4방탐색을함과 동시에 불도 4방으로 퍼져나간다는것을 생각해야 한다. 나는 이부분에서 막혀서 다른글을 참고했다.
대략적인 풀이방식은 이렇다 :
1. 불과 지훈이의 좌표를 각 큐에 담는다.
2. 불이 먼저 퍼져나가며 퍼져나간 불의 위치를 큐에 담는다.
3. 지훈이가 4방탐색을 하며 지훈이가 갈 수 있는 모든위치의 좌표를 큐에 담는다.
4. 이미 퍼져나간 불은 한 번더 퍼져나갈필요가없다. 새롭게 퍼져나간 불만 다시 퍼져나간다. (애초에 이미 퍼져나간불은 큐에 좌표가 없다.)
5. 3에서 4방탐색을 하며 지훈이가 갈 수 있는 모든 위치에서 다시 4방탐색을 하며 탈출구를 찾는다.
6. 4, 5를 반복한다.
7 - 1. 지훈이의 좌표가 지도 밖을 나갈경우 정답을 출력해준다.
7 - 2. 지훈이가 더이상 새롭게 이동할수 있는 위치가 없을 경우 jihoon 큐에는 더이상 값이 안담겨있기 때문에 IMPOSSIBLE을 출력해준다.
디버깅모드를 하고 지도의 모습을 시뮬레이션한것을 보면 약간은 신기하다. 여기서 중요한점은 불이 지훈이의 위치가 담긴 자리까지 불이 번져나가며 덮어버리는 경우가 있는데. 단순히 지도에서만 그렇고 지훈이의 좌표는 jihoon 큐 안에 담겨있기 때문에 문제없다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
int result = 0;
int left = 0;
int right = arr[N - 1] - arr[0]; // 최대 간격
while (left <= right) {
int cnt = 1;
int cur = arr[0]; // 첫 번째 집부터 시작
int mid = (right + left) / 2; //공유기 설치의 최소 간격
for (int i = 1; i < N; i++) { // 첫 번째집은설치했으니 두번째집부터 시작
if (arr[i] - cur >= mid) {
cnt++;
cur = arr[i]; // 현재 바라보는 인덱스(커서)를 설치한 집으로 이동
}
}
if (cnt >= C) { // 공유기간의 거리를 적당히 설정해서 최소 C개만큼 설치했을 경우
result = mid;
// 좀더 좋은 결과값을 찾기위해 간격을 넓혀본다
left = mid + 1;
} else {
// 결과값을 찾기위해 간격을 좁힌다
right = mid - 1;
}
}
System.out.println(result);
}
}
[설명]
공유기를 설치한 집과 다음 설치할 집과의 간격이 mid 이상일 경우에만 cnt를 1씩 증가시킨다. for문이 끝난 후 cnt 의 값이 C이상일 경우 좀더 최적의 해를 찾기위해 간격을 넓혀서 재탐색해본다. 우리는 최댓값을 찾는것이기 때문이다. cnt의 값이 C보다 적을 경우 간격을 좁혀 해를 재탐색한다.
import java.io.*;
import java.util.*;
public class Main {
static int R, C, answer = 0;
static char[][] graph;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static HashSet<Character> alphabet;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
graph = new char[R][C];
for (int i = 0; i < R; i++) {
String input = br.readLine();
for (int j = 0; j < C; j++) {
graph[i][j] = input.charAt(j);
}
}
alphabet = new HashSet<>(); // HashSet 초기화
back(0, 0, 1); //
System.out.println(answer);
}
static void back(int x, int y, int count) {
answer = Math.max(answer, count);
alphabet.add(graph[x][y]);
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
if (!alphabet.contains(graph[nx][ny])) { // 처음 방문한 알파벳일 경우
back(nx, ny, count + 1);
}
}
}
alphabet.remove(graph[x][y]); // 이전 상태로 돌아가기 위해 제거
}
}
[설명]
백트래킹 문제이다.
일반적인 백트래킹 알고리즘과 다른점은 단순 방문했던 자리를 체크하는게 아니라 똑같은 알파벳이 아닌자리를 체크해줘야한다. 그 부분은 HashSet을 이용해 체크해주었다. 그리고 alphabet.remove()를 활용해 지나온 알파벳을 지우며 이전상태로 돌아간다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int S = Integer.parseInt(st.nextToken());
int[] arr = new int[N+1];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int answer = Integer.MAX_VALUE;
int left = 0;
int right = 0;
int sum = 0;
while (left <= N && right <= N) {
if (sum >= S) {
answer = Math.min(answer, right - left);
sum -= arr[left++];
} else if (sum < S) {
sum += arr[right++];
}
}
System.out.println(answer==Integer.MAX_VALUE ? 0 : answer);
}
}
[설명]
투포인터 알고리즘을 활용한다.
sum 이 S보다 작을 경우 sum += arr[right++]를 하고
sum이 S보다 크거나 같을 경우 sum -= arr[left--]를 해준다. 그리고 동시에 right - left를 해주어 더 작은값을 출력해준다.
import org.w3c.dom.html.HTMLParagraphElement;
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int answer = 0;
for (int i = 0; i < N; i++) {
int left = 0;
int right = N - 1;
int target = arr[i];
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) { // sum이 target과 같을 경우
if (left != i && right != i) { // left와 right가 같은 수가 아닐경우
answer++;
break;
} else if (left == i) { // 현재 탐색하려는 숫자를 사용하면 안됨
left++;
} else { // 현재 탐색하려는 숫자를 사용하면 안됨
right--;
}
} else if (sum < target) { //sum이 target보다 작을 경우
left++;
} else { // sum이 target보다 클 경우
right--;
}
}
}
System.out.println(answer);
}
}
[설명]
투 포인터로 풀었다. 배열을 입력받은 후 arr[left] 와 arr[right]를 더한값을 target 과 비교해가며 left를 늘리고 right를 줄이며 탐색한다.
if (left != i && right != i) { // left와 right가 같은 수가 아닐경우
answer++;
break;
} else if (left == i) { // 현재 탐색하려는 숫자를 사용하면 안됨
left++;
} else { // 현재 탐색하려는 숫자를 사용하면 안됨
right--;
}
여기서 else if 구문과 else 구문이 이해가 너무안가서 1시간 넘게 이해를 못하고있었다.
예를 들어 현재 3번 인덱스를 target으로 두고 탐색하고있을 때, 3번인덱스 + X인덱스를 더한값을 찾으려고 했을 경우라는 의미이다. 3번인덱스를 찾으려는데 3번인덱스를 더해서 찾는건 말이 안되기 때문이다.
