고양멍멍이

[문제링크] 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 0. 백트래킹 / 구현 문제 1. 백트래킹을 위하여, 상어의 각 이동 단계마다 map과 물고기 방향 정보를 저장한다 2. 해당 상황에서 물고기 이동 - 가능한 모든 상어 이동에 대해 재귀를 돌린 다음, 저장해둔 정보를 복원하고 이전 단계로 돌아간다 3. 각 재귀 단계에서 먹은 물고기 번호의 합을 저장, 더이상 진행 불가능할때 전역변수인 maxEat과 비교, 갱신한다 import java.io.BufferedReader; import ..

[문제링크] 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 1. 사용한 풍선은 표시해두고, 지나가더라도 카운트하지 않는다 2. 양 끝 간 이동 처리를 위해, 증감시 N으로 나머지 연산 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ public static void main(String[] args)throws Exception ..

[문제링크] 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 0. 단순 구현 + 그래프 탐색 문제 1. 주어진 l 값에 맞게, 각 칸을 회전시킨다 2. 다른 얼음과 2칸 이하로 맞닿은 칸들을 체크한다 3. 해당 칸들을 녹인다 4. 1~3 반복 5. 다 녹은 후 dfs를 실행, 가장 큰 덩어리의 크기를 찾는다 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; publi..

[문제링크] 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 0. 단순 구현 문제 1. 구름을 이동하고 -> 대각선 물 양을 증가시키고 -> 새 구름을 생성한다 의 반복 2. 구름이 사라진 칸은 boolean 배열로 관리한다 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public..

[문제링크] 17276번: 배열 돌리기 각 테스트 케이스에 대해 회전 연산을 마친 후 배열의 상태를 출력한다. n줄에 걸쳐 각 줄에 n개의 정수를 공백으로 구분하여 출력한다. www.acmicpc.net 0. 단순한 구현 문제 1. 4개의 대각선을 옮기는 작업을 한다 두 수를 swap하듯, 하나를 백업하고 후에 복구 2. -X 각도로의 회전은 360-X 각도의 회전과 같다 별도의 함수를 만들지 않고, 45도 회전 함수를 동일하게 사용 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ static int[][] map; static int n,d;..

[문제링크] 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 0. 각 알파벳의 총 크기를 구해, 그리디하게 숫자를 부여한다 ex) AB, BC의 경우, A는 10의자리에 1번 나오니 10, B는 11, C는 1 B가 가장 크므로 9, 그다음인 A에 8, C에 7을 주는 식 1. 모든 수에 대해 알파벳별로 등장 자릿수에 따라 값을 누적시킨다 2. 종료시 내림차순 정렬, 값이 큰 순으로 9~0까지 값을 부여하며 진행한다 알파벳이 10개 이하로 존재하여도, tmp배열의 초깃값이 0이므로 문제 없음 import..

[문제링크] 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 0. m 이하의 cost로 방문 가능한 노드가 가장 많은 노드 찾기 다익스트라를 n번 돌리거나, 플로이드-와샬 진행 1. 편의를 위해, 갈 수 없는 노드는 큰 값(2000)으로 초기화한다 최대 거리가 15, 노드가 100개이므로 두 노드의 거리는 15*99=1485가 최대값이다 2. 노드 간 거리 정보를 저장하고, 플로이드-와샬을 진행해 각 노드간 거리를 구한다 3. 각 노드 별 방문 가능한 노드들로부터 획득 아이템 갯수를 종합, 최댓값을 출력한다 impo..

[문제링크] 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 0. 구현문제. 요구사항을 잘 구현한다 1. 톱니바퀴의 연쇄 회전 : 회전 여부를 저장하는 boolean 배열과 재귀로 진행 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ static boolean[][] wheel; static boolean[] isTurn; public static..

[문제링크] 16919번: 봄버맨 2 첫째 줄에 R, C, N (1 ≤ R, C ≤ 200, 1 ≤ N ≤ 109)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 0. 같은 코드로 봄버맨1(링크)도 해결 가능하다 1. 시작 직후를 제외하면, 빈공간을 채운다 - 터진다 - 빈공간을 채운다 - 터진다 - ... 순으로 반복되게 된다 2. 특정 시점 x에 폭탄이 놓인다면, x+1시점에는 x-2때 설치된 폭탄들이 터지며 방금 놓인 폭탄 중 일부가 제거된다 이때 제거된 폭탄들은, x시점에 놓인 폭탄들 중 외곽과 닿은 폭탄들이다 3. x+2시점에는 새 폭탄이 설치되고, x+3시점에는 x때 설치된 폭탄들이 터지며 x+2..

[문제링크] 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 1. 현재 노드 x를 기준으로, 전위 순회는 x-[왼쪽]-[오른쪽] 의 순서로, 중위 순회는 [왼쪽]-x-[오른쪽]의 순서로 만들어진다 2. 즉, 전위 순회 결과의 첫 노드를 기준으로, 중위 순회의 왼쪽과 오른쪽을 분리할 수 있다. 3. 또한 왼쪽과 오른쪽 subtree에 대해서도 동일한 작업으로 분리할 수 있다. 최종적으로 tree의 크기가 1이 되면, leaf 노드가 된다 4. tree를 입력받아, root 노드를 만들어 반환하는 함수..