고양멍멍이

[문제링크] 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 0. 내구도/데미지 값을 고려해서 가능한 많은 계란을 깨는 문제 1. 재귀를 사용해서 모든 경우의 수를 진행한다 현재 계란이 깨지지 않았다면, 이걸로 다른 깨지지 않은 계란을 친다 깨졌다면, 그냥 넘어간다 다음번 계란으로 넘어가서 반복한다 모든 계란에 대해 시도했다면, 종료하고 깬 계란 수를 관리한다 계산 편의, 효율을 위해 깨진 계란의 수를 인자로 관리한다 2. 위 과정에서 나온 값들 중 최댓값을 저장, 출력 import java.io..

[문제링크] 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 0. 상어와 가장 먼 칸에서의 상어와의 거리를 구하는 문제 1. 이동 방향이 8방향이므로, dir 배열을 8방향으로 구성한다 2. 상어를 기준점으로 주변 칸을 bfs로 탐색한다 위치와 거리 정보를 저장하는 class를 만들어 사용한다 탐색하며 거리 정보를 칸에 저장한다 탐색 중 특정 지점에 현재 거리보다 작거나 같은 값이 저장되있다면, 다른 상어가 더 가깝게 있다는 뜻이므로 탐색을 정지한다 3. 모든 상어로부터 bfs가 종..

[문제링크] 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 0. 최소한의 갯수로 목표 금액을 맞추는 문제 1. 모든 고액권은 소액권의 n배수로 떨어지므로, 항상 가장 큰 액수부터 선택하는게 유리하다 그리디 알고리즘 2. 목표 금액을 초과하지 않는 선에서, 가능한 많은 금액을 고액권부터 채워나간다 3. 목표 금액이 완성되면, 최종 갯수를 출력 import java.io.BufferedReader; import java.io.InputStreamRe..

[문제링크] 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 0. 가장 큰 음식물 덩어리의 크기 구하기 상하좌우로 연결되 있을 경우 한 덩어리로 본다 1. 음식물의 여부를 boolean 배열로 표현한다 2. 탐색 중 음식물 발견시, dfs 탐색으로 진입한다 이미 탐색한 음식물 제거 (현재 위치 false로 변경) 상하좌우 4방향 각각으로 음식물이 있으면 진행한다 최종적으로 연결된 모든 음식물을 지우고, 그 크기를 반환 3. 모든 음식물 덩어리중 가장 큰 값 유지, 출력..

[문제링크] 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 0. 모든 leaf 노드에 말이 있으며, 한 번에 하나씩 부모로 올리는 게임 모든 leaf 노드의 차수의 합에 따라 승/패를 알 수 있다 (짝수면 선공 패배, 홀수면 선공 승리) 1. 시작 노드는 1번으로 고정이므로, BFS를 이용해 모든 노드를 탐색, leaf 여부 및 depth를 저장한다 2. BFS를 진행할 때 연결된 노드에 이미 depth 정보가 있다면 : 이미 방문한 노드, 즉 부모 노드이다 depth 정보가 없다면 : 방문하지 않은 노드, ..

[문제링크] 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 0. 모든 선생님의 시야(일직선)를 피하도록 장애물을 설치할 수 있는지 묻는 문제 맵의 크기가 최대 6*6으로 작고, 선생님의 수도 5 이하로 적으니 brute-force로 해결 가능하다 1. setWall 재귀를 3번 진행하며 가능한 모든 조합으로 벽을 설치한다 2. 3개의 벽이 설치됬다면, 모든 선생님 기준으로 4방향 검사, 학생이 보이는지 검사한다 학생의 수(최대 30)에 비해 선생의 수(최대 5)가 적기 때문 3. 단 한 선생님이라도 ..

[문제링크] 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 0. 완전 이진 트리를 중위 순회한 결과가 주어졌을때, 원래의 트리를 복원하는 문제 1. 완전 이진 트리의 특성상, 왼쪽 subtree와 오른쪽 subtree의 크기가 동일하다 중위 순회는 왼쪽 - 자신 - 오른쪽 순서로 이루어지므로, 정 가운데 번호가 항상 root노드이다 2. 시작-끝 값으로 subtree 정보를 유지하면서, 가운데(root) 정보를 저장하며 재귀를 진행한다 재귀의 깊이에 따라 각 list에 저장 subt..

[문제링크] 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문 www.acmicpc.net 0. a-b 두 노드간 최단 거리 구하기 1. 다익스트라, 벨만 포드 등 다양하게 풀이 가능하다 2. bfs로 탐색, 목표 노드가 발견되는 즉시 탈출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue;..

[문제링크] 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 ..

[문제링크] 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;..