문제 이해n×m 노트북(paper)에 k개의 스티커를 차례대로 붙인다. (우선순위: 왼쪽 위)이미 붙인 칸과 겹치면 안 되며, 한 번 붙이면 고정.모든 위치에 붙일 수 없으면 스티커를 0°, 90°, 180°, 270° 회전하여 시도.최종적으로 스티커가 붙은 칸의 총 개수를 출력. 풀이 흐름1. 탐색현재 스티커를 붙일 수 있는 위치를 왼쪽 위부터 탐색한다.(0,0)부터 (n-r, m-c)까지 붙일 수 있는 위치를 순서대로 확인한다.2. 스티커 붙이기스티커와 종이의 충돌을 검사한다. (둘다 1인 경우)해당 위치에 스티커의 1인 칸과 종이의 1인 칸이 한 번이라도 겹치면 실패 (return false)전부 안 겹치면 종이에 스티커를 붙인다. (붙이는 위치의 paper 값 = 1)3. 회전위에서 스티커를 못 ..

문제https://www.acmicpc.net/problem/11437 문제 풀이DFS로 parent/depth 저장 → 깊이 맞추기 → 함께 올라가면서 같아지는 지점 반환 트리 DFS로 각 노드의 부모, 깊이 저장하기루트부터 자식으로 내려가면서 parent, depth 배열에 저장루트(1)는 부모를 자기 자신(1)으로, 깊이는 0으로 (dfs(1, 1, 0)) LCA 구하기깊이 맞추기더 깊은 쪽을 부모로 올려서 depth[a] == depth[b]로 만듦.공통 조상 찾기a == b가 될 때까지 둘 다 parent로 올라감.같아지면 그 노드가 LCA. 유의할 점 (예외)a, b가 같은 노드이거나, 한쪽이 다른 쪽의 조상일 수 있다.이때 LCA는 그 노드 자신이어야 한다. 잘못된 코드while (pare..

문제https://www.acmicpc.net/problem/21608 문제 이해N×N 교실의 빈 좌석에 학생들을 순서대로 앉힌다.각 학생은 좋아하는 4명의 친구가 있고, 좌석 배치는 아래 우선순위를 따른다:인접 4칸에 좋아하는 학생이 가장 많은 자리위 조건이 같다면 인접 빈칸이 많은 자리그래도 같다면 행 번호가 작은 자리그래도 같다면 열 번호가 작은 자리모든 학생을 배치한 후 만족도를 계산:인접 4칸의 좋아하는 학생 수에 따른 점수 = {0, 1, 10, 100, 1000} 구현 흐름입력학생 배치 순서 students[]preferences: 각 학생 → 좋아하는 학생 4명(Set)seats: 교실 좌석 상태 (N×N)배치findSeat(student)에서 모든 빈칸을 검사해 우선순위에 가장 맞는 좌석..

문제https://www.acmicpc.net/problem/20056 문제 이해N×N 격자에서 파이어볼들이 K번 이동·합체·분리된다.각 파이어볼: 위치 (r,c), 질량 m, 속력 s, 방향 d(0~7).한 칸에 2개 이상 모이면 하나로 합친 뒤 4개로 분리새 질량 = ⌊(합 질량)/5⌋ (0이면 소멸)새 속력 = ⌊(합 속력)/개수⌋새 방향: 모두 짝/홀만 있었으면 {0,2,4,6}, 섞여 있으면 {1,3,5,7} 구현 흐름입력fireBall 리스트에 모든 파이어볼 저장map[r][c]에는 해당 칸에 존재하는 파이어볼 저장K번 반복이동 move()모든 파이어볼을 방향·속력대로 이동이동 후 map에 삽입합체 후 4분리 divide(int r, int c)map[i][j] >= 2인 칸만 divide(i..

문제https://www.acmicpc.net/problem/16236 문제 이해N×N 공간: 빈 칸(0), 물고기(1~6), 상어(9)상어의 크기: 2.상어는 자신의 크기보다 작은 물고기만 먹을 수 있고, 자신의 크기와 같거나 작은 칸은 지나갈 수 있다.가장 가까운 물고기를 먹는다.거리가 같으면 가장 위(행이 작은) 물고기그다음 가장 왼쪽(열이 작은) 물고기물고기를 자신의 크기만큼 먹으면 크기가 1 증가더 이상 먹을 수 없을 때까지 이동한 총 시간(=이동 칸 수 합) 을 구한다. 아이디어최단거리 탐색: BFS거리 → 행 → 열 우선순위: 우선순위 큐 구현상태curSize : 현재 상어 크기(초기 2)cnt : 현재 크기에서 먹은 물고기 수(크기만큼 먹으면 증가)time : 누적 이동 시간방문 배열과 큐..

문제https://www.acmicpc.net/problem/2533 문제 이해SNS 네트워크는 트리(사이클 없음) 로 주어진다.어떤 사람이 정보를 전달받으려면 그 사람의 이웃 중 적어도 한 명은 ‘얼리어답터’ 여야 한다.모든 사람이 정보를 전달받도록 할 때, 필요한 얼리어답터의 최소 수를 구한다.TIP: “모든 간선마다 양 끝점 중 최소 한 쪽은 선택되어야 함” 이라고 생각하면 이해하기 쉽다. 풀이 아이디어: 트리 DP루트를 1로 잡고 DFS로 트리를 내려가며 탐색한다. 상태 정의dp[0][node] : node가 얼리어답터가 아닐 때, node의 서브트리에서 필요한 최소 얼리어답터 수dp[1][node] : node가 얼리어답터일 때, node의 서브트리에서 필요한 최소 얼리어답터 수 점화식현재 정점..

문제https://www.acmicpc.net/problem/15486 문제 이해N일 동안 가능한 상담 일정이 주어진다.상담의 기간, 수익N + 1일째 되는 날 퇴사하기 위해, 퇴사 전(N일 내)에 끝나는 상담들을 선택해 최대 수익을 구한다.하루에 하나의 상담만 할 수 있어서, 상담을 시작하면 해당 상담 기간 동안 다른 상담은 할 수 없다.끝나는 날이 N일을 넘어가면 그 상담은 수행할 수 없다. DP 구현dp[i]: i일까지의 최대 이익전날 이익 저장 dp[i] = max(dp[i], dp[i-1])i일에 상담을 시작끝나는 날: end = i + consults[i].t - 1퇴사 전에 끝나는 상담만 유효: end i - 1일까지의 최대 수익에 이번 상담의 수익을 더해서 최댓값 반영dp[end] = ma..

문제https://www.acmicpc.net/problem/16930 문제 이해N×M 체육관에 빈 칸(.)과 벽(#)이 있다.한 번 이동할 때, 상·하·좌·우 중 한 방향으로 1칸 이상 k칸 이하를 이동할 수 있다.시작점에서 도착점까지 이동하는 최소 시간을 구한다. 문제 풀이BFS를 이용하여 각 칸에 도달하는 최소 시간을 기록한다.상하좌우(dr, dc) 네 방향에 대해 1..k칸 이동하는 경우를 탐색한다. 상태 정의map[r][c] = -1: 미방문, -2: 벽으로 초기화BFS 탐색하면서 해당 칸에 도달한 최소 시간 저장 탐색 조건미방문: map[nr][nc] == -1지금이 처음 도달이므로 map[nr][nc] = map[cur.r][cur.c] + 1로 갱신하고 큐에 넣는다.이미 더 빠른 시간에 도..

문제https://www.acmicpc.net/problem/14503 문제 이해N×M 크기의 방이 주어진다.로봇 청소기는 아래 규칙에 따라 작동한다.현재 위치를 청소한다.현재 위치에서 왼쪽 방향부터 차례대로 탐색한다.아직 청소하지 않은 빈 칸이 있으면 그 칸으로 이동 후 1번으로 돌아간다.없으면 바라보는 방향을 유지한 채로 한 칸 후진할 수 있으면 후진, 아니면 작동을 멈춘다.최종적으로 로봇 청소기가 청소하는 칸의 개수를 출력한다. 문제 풀이시뮬레이션 구현청소할 때마다 카운트를 증가네 방향 중 청소되지 않은 칸이 있으면 회전 후 이동네 방향 모두 불가능하면 후진, 후진도 불가능하면 종료 코드import java.util.*;import java.io.*;public class Main { static ..

문제https://www.acmicpc.net/problem/1946 문제 이해지원자마다 서류 등수, 면접 등수가 주어진다.한 지원자 A가 다른 지원자 B보다 서류/면접 모두에서 등수가 낮으면 탈락한다.최종적으로 선발될 수 있는 지원자 수의 최댓값을 구한다. 문제 풀이아이디어서류가 더 좋은 지원자를 앞에서부터 보는데, 지금까지 본 사람들 중 면접도 더 좋지 않으면(= 기존 최솟값보다 작지 않으면), 앞선 누군가에게 둘 다 밀리게 되므로 탈락 처리된다.구현서류 등수를 기준으로 오름차순으로 정렬한다.arr[서류 등수] = 면접 등수 형태로 저장한다.앞에서부터 훑으며, 현재까지의 면접 등수 최솟값을 갱신하는 지원자만 카운트한다.맨 처음(서류 1등)은 무조건 선발한다.(ans = 1, minRank = arr[..