총 10분 중 11분
2001
시즌 2개, 그리고 영화
시즌 2:
5화
“아일랜드”
출연: 이나영, 김민준, 김민정, 현빈
장르: 애초에 역경을 딛고 이룩하는 숭고한 사랑이란 없다. 그 역경 자체가 사랑이다.
프로그램 특징: 그 곳에서 살아남는 사랑이 어떤 모습으로 걸어오는지 기다려 보고 싶다.
장르: 애초에 역경을 딛고 이룩하는 숭고한 사랑이란 없다. 그 역경 자체가 사랑이다.
프로그램 특징: 그 곳에서 살아남는 사랑이 어떤 모습으로 걸어오는지 기다려 보고 싶다.
회차
-
[Java][BOJ 19941] 햄버거 분배0626분문제 링크문제 파악식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K, 사람과 햄버거의 위치가 주어졌을 때 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오. 첫 줄에 N과 K가 주어지고 다음 줄에 사람과 햄버거의 위치가 문자 P(사람)과 H(햄버거)로 주어진다. 1 1 20 1HHPHPPHHPPHPPPHPHPHP //820 2HHHHHPPPPPHPHPHPHHHP //7접근 방법햄버거사람햄버거사람햄버거사람햄버거햄버거사람사람햄버거사람123456789101112K = 2인 경우에는 6명 모두가 햄버거를 먹을 수 있다.2번 위치에 있는 사람: 1번 위치에 있는 햄버거4번 위치에 있는 사람: 3번 위치에 있는 햄버거6번 위치에 있는 사람: 5번 위치에 있는 햄버거9번 위치에 있는 사람: 7번..
-
[Java][BOJ 17484] 진우의 달 여행(small)0619분문제 링크문제 파악지구와 달 사이 공간의 행렬 N x M (2≤ N, M ≤ 6)에서 달 여행에 필요한 최소 연료 값을 출력하라같은 방향으로 두 번 이동할 수 없다.접근 방법1. dfs에서 y가 7(높이)이되면 pq에 넣어 가장 적은 비용을 출력한다.2. dp는 dp[i][j] i 행 j 열이 = dp[i-1][j-1 or j or j+1] + dp[i][j] 1. 같은 방향인지 확인하기 위해 dir를 노드에 추가하고, 이전과 같은 dir면 멈추는 조건을 추가해야 한다.2. 재귀에서 탈출했을 때 visited false 처리재귀는 stack처럼 동작하기 때문에 달을 찍고 return하면 두번째 뒤 점에서 다시 달까지 시도코드 구현import java.util.*;public class Main { ..
-
[Java][BOJ 22860] 폴더 정리0612분문제 링크문제 파악main 폴더 하위에 있는 폴더의 총 개수 N, 파일의 총 개수 M상위 폴더 이름 P, 폴더 또는 파일의 이름 F, 폴더면 1 파일이면 0Q개의 쿼리는 main 부터 존재하는 경로에 대한 폴더인데, 폴더 하위에 있는 파일의 종류 개수와 파일의 총 개수를 출력하라4 1main FolderA 1FolderA FolderB 1FolderB FolderC 1FolderC FolderD 1FolderD File1 03mainmain/FolderAmain/FolderA/FolderB/FolderC/FolderD출력1 11 11 1 접근 방법각 폴더마다 파일 Set로 중복 처리하고, Parent - Folder(File) 리스트를 dfs 탐색하면서 파일 개수 카운트1. 부모 폴더에 따라 존재하는 파..
-
[Java][BOJ 17386] 선분 교차10605분문제 링크문제 파악2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자.L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다.세 점이 일직선 위에 있는 경우는 없다.접근 방법L1의 두 점을 기준으로, L2의 CCW의 부호가 반대로 나오면 교차, 아니면 0 출력+ L2와 L1의 두 점의 관계도 봐야 선분 교차 판정이 가능하다. CD가 AB를 가로질러도 AB가 CD를 가로지르지 않는 특수 케이스를 배제할 수 없기 때문이다. 코드 구현import java.util.*;public class Main { public static void main(String[] args) { Scanner ..
-
[Java][BOJ 11758] CCW: Counter-Clockwise0604분문제문제 파악첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다.P1, P2, P3를 순서대로 이은 선분이 반시계 방향을 나타내면 1, 시계 방향이면 -1, 일직선이면 0을 출력한다.접근 방법기하의 핵심이론 CCWCCW(Counter-Clockwise): 평면상의 3개의 점과 관련된 점의 위치 관계를 판단하는 알고리즘이를 이해하기 위해선 벡터의 외적 개념 이해가 필요하다. CCW = (X1Y2 + X2Y3 + X3Y1) - (X2Y1 + X3Y2 + X1Y3)벡터의 외적이 |CCW| / 2는 세 점..
-
트리 계산을 위한 배열(인덱스) 표현0530분*'Do it! 알고리즘 코딩 테스트 자바편'을 참고했습니다.직관적이면서 편리한 트리 자료구조는 "배열"인덱스01234567값ABCDEFNoneG트리의 노드와 배열의 인덱스 사이 상관관계이동 목표 노드인덱스 연산제약 조건(N = 노드)root nodeindex = 1 parent nodeindex = index / 2not root nodeleft child nodeindex = index * 2index * 2 right child nodeindex = index * 2 + 1index * 2 + 1 위 인덱스 연산 방식은 segment tree나 LCA(lowest common ancestor) 알고리즘에서도 기본이 되는 연산이므로 숙지해야 한다.
-
[Java][프로그래머스] 신고 결과 받기0530분문제 파악매개변수이용자의 ID가 담긴 문자열 배열 id_list ["muzi", "frodo", "apeach", "neo"]각 이용자와 이용자가 신고한 이용자의 ID 정보가 담긴 문자열 배열 report ["muzi frodo","apeach frodo","frodo neo","muzi neo","apeach muzi"]정지 기준이 되는 신고 횟수 k각 유저는 다른 유저를 신고할 수 있다(중복 신고는 가능하나 신고 1회로 처리). 이때 신고를 k번 이상 받으면 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송한다.id_list에 담긴 id 순서대로 각 유저가 받은 결과 메일 수를 배열로 담아 return접근 방법1. String[] report -> Set report..
-
[JAVA][BOJ 2098] 외판원 순회와 비트 연산0521분문제링크문제 파악TSP(Traveling Salesman Problem) 가중치가 있는 단방향 그래프를 가장 작은 비용을 들이면서 순회하는 경로를 구해라!첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 도시 i에서 j로 이동할 수 없는 경우에는 W[i][j]=0이라고 한다항상 순회할 수 있는 경우만 입력으로 주어진다.접근 방법DP[현재도시][현재까지 방문한 도시 리스트] = 남은 모든 도시를 경유하는 데 드는 최소 비용남은 도시를 경유하는 데 드는 최소 비용은 DFS로 구현리스트를 변수 1개에 ..
-
[JAVA][BOJ 1256] 조합: 사전 찾기0515분문제링크문제 파악N개의 'a', M개의 'z'로 사전을 만들었다. 알파벳 순서로 수록된 사전에서 K번째 문자열 구하기사전에 있는 수가 K보다 작으면 -1 반환N개의 'a', M개의 'z', K번째 문자열1 ≤ N, M ≤ 1001 ≤ K ≤ 1,000,000,000접근 방법각 자리 수까지 만들 수 있는 문자열 개수 중복한 문자를 가지기 때문에 만들 수 있는 문자열의 개수는 N+M개 중 N개 또는 M개를 택하는 것과 같다.순열과 똑같이 전체 중에서 칸막이를 넣는다고 생각하면 된다.그리고 순열의 nCr = n-1 C r-1 + n-1 C r 을 이용하면 DP가 된다. DP부문 문제가 해결된 상황에서 마지막 데이터의 선택 여부에 따른 경우의 수 계산하는 것이다.DP[5][3] = DP[4][2] + DP[..
Algorithm/Greedy
[Java][BOJ 19941] 햄버거 분배
728x90
반응형
문제 링크
문제 파악
식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K, 사람과 햄버거의 위치가 주어졌을 때 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오. 첫 줄에 N과 K가 주어지고 다음 줄에 사람과 햄버거의 위치가 문자 P(사람)과 H(햄버거)로 주어진다.
- 1 <= N <= 20000
- 1 <= K <= 10
20 1
HHPHPPHHPPHPPPHPHPHP //8
20 2
HHHHHPPPPPHPHPHPHHHP //7
접근 방법
햄버거 | 사람 | 햄버거 | 사람 | 햄버거 | 사람 | 햄버거 | 햄버거 | 사람 | 사람 | 햄버거 | 사람 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
K = 2인 경우에는 6명 모두가 햄버거를 먹을 수 있다.
- 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
- 4번 위치에 있는 사람: 3번 위치에 있는 햄버거
- 6번 위치에 있는 사람: 5번 위치에 있는 햄버거
- 9번 위치에 있는 사람: 7번 위치에 있는 햄버거
- 10번 위치에 있는 사람: 8번 위치에 있는 햄버거
- 12번 위치에 있는 사람: 11번 위치에 있는 햄버거
처음에 그리디로 생각했는데 9번의 경우 가장 가까운 값으로 먹으면 10번이 11번 햄버거를 먹어서 12번이 아무것도 못먹게 된다.
그래서 백트래킹인건가? dfs로 각 P마다 1-K번 모두 점프 시도해보았다. (근데 가장 가까운 값을 먹는게 아니라 가장 작은 인덱스 값부터 먹는 그리디였으면 가능했다. )
- 처음에는 한 칸 점프, 만약 K가 1보다 크면, 2칸 점프해서 dfs... K칸까지 점프하는 dfs 실행 후 Math.max로 출력
- String 에서 P를 찾아 이동 가능한 거리를 for문으로 돌면서 먹을 수 있는 지 확인한다.
- 먹을 수 있으면 햄버거 eaten 표시와
사람별로 먹었는지를 나타내는 pEaten를 True 표시한다. - 먹을 수 없거나 H면 idx+1해서 다음 dfs 실행한다.
- 인덱스가 String 길이가 되면 종료
static char[] line;
static boolean[] eaten;
static boolean[] pEaten;
dfs(0,0);
dfs(int idx, int cnt) {
if (idx >= N) {
maxCnt = Math.max(maxCnt, cnt);
return;
}
if (line[idx] == 'P') {
boolean matched = false;
for (int jump = -K; jump <= K; jump++) {
int target = idx + jump;
if (target < 0 || target > N-1) continue;
if (line[target] == 'H' && !eaten[target]) {
// 먹기
eaten[target] = true;
dfs(idx + 1, cnt + 1);
eaten[target] = false;
matched = true;
}
}
if (!matched) dfs(idx + 1, cnt); // 못 먹고 넘어감
} else {
dfs(idx + 1, cnt); // 사람이 아닌 경우 그냥 넘어감
}
}
는 시간초과가 난다. 백트래킹이고. 그리디도 시간복잡도는 O(20000*20)로 똑같을 것 같은데 아니었다.
코드 구현
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
String line = sc.next();
char[] arr = line.toCharArray();
boolean[] eaten = new boolean[N];
int count = 0;
for (int i = 0; i < N; i++) {
if (arr[i] == 'P') {
// 앞뒤로 k칸 범위 탐색
for (int j = i - K; j <= i + K; j++) {
if (j < 0 || j >= N) continue;
if (arr[j] == 'H' && !eaten[j]) {
eaten[j] = true;
count++;
break; // 한 사람은 햄버거 하나만 먹음
}
}
}
}
System.out.println(count);
}
}
배우게 된 점
백트래킹은 시간복잡도가 더 작을 줄 알았는데.. 아니었다. 20개의 문자에 대해 K개의 선택을 하니까 20^K로 계산해야 한다.
질문
728x90
'Algorithm > Greedy' 카테고리의 다른 글
[JAVA][BOJ 1911] 흙길 보수하기 - 그리디 pq (3) | 2025.04.24 |
---|
2025:06:26
Algorithm/Greedy
[Java][BOJ 19941] 햄버거 분배