본문 바로가기

Algorithm/BOJ47

원티드 쇼미더코드 3회차 - C번 미팅 https://www.acmicpc.net/problem/27212 27212번: 미팅 오늘은 A대학의 학생 $N$명과 B대학의 학생 $M$명이 만나는 날이다. 이들이 만나는 장소에는 크고 길이가 긴 식탁이 하나 있어서, 한쪽에는 A대학 학생이, 다른 한쪽에는 B대학 학생이 앉을 예정이 www.acmicpc.net 양 대학의 N명과 M명이 일렬로 서서 악수를 하는데, 팔이 교차하지 않게 악수를 할 수 있을 때, 서로 얻을 수 있는 만족도 합의 최댓값을 구하는 문제이다. 처음에 이분그래프인가? 라고 생각도 해보고, 사람 순서대로 악수를 하기 떄문에 백트래킹을 이용해서 조합으로도 풀어봤다(시간초과) 악수를 할 수도 있고, 안할 수도 있기 때문에 경우의 수가 너무 많아지기 때문에 바로 DP 방식을 고민했다. .. 2023. 1. 15.
원티드 쇼미더코드 3회차 - B번 도넛 행성 https://www.acmicpc.net/problem/27211 27211번: 도넛 행성 준겸이는 $N \times M$칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 www.acmicpc.net 그림만 보면 허걱하는데 내용을 보면 전형적인 2차원 배열 내에서의 연결 요소 문제이다. 2차원 그리드 전체를 순회하면서 dfs 혹은 bfs 탐색으로 같은 구역으로 묶이는 지역들을 방문하면 된다. 다만 햇깔리는 점은 그리드 위아래, 왼쪽오른쪽이 서로 구 처럼 연결되어있으므로 그리드 범위를 넘어가면 반대지역으로 치환해주면 된다 #include using namespace std; #defi.. 2023. 1. 15.
원티드 쇼미더코드 2022년 3회차 - A번 신을 모시는 사당 원티드 쇼미더코드 3회차 문제가 백준에 올라와서 정리해봄 https://www.acmicpc.net/problem/27210 27210번: 신을 모시는 사당 칠할 수 있는 돌상의 개수에 제한은 없으며, 반드시 연속한(인접한) 돌상들만 칠할 수 있음(띄엄띄엄 칠할 수 없음)에 유의하라. www.acmicpc.net 돌상 N개가 왼쪽 혹은 오른쪽을 보고 있는데, 연속된 곳을 색칠했을 때 얻을 수 있는 깨달음의 최대값을 구하는 문제이다. | (왼쪽을 바라보는 금색 돌상의 개수) - (오른쪽을 바라보는 금색 돌상의 개수) | = 깨달음 값 N이 최대 10만이여서 N^2 미만의 복잡도로 풀어야했다. 부분 수열 합의 최대값을 구하는 문제가 되기 때문에 카데인 알고리즘의 O(N) 시간복잡도를 생각해서 부분합을 구하는.. 2023. 1. 15.
BOJ 2228 - 구간 나누기(DP) - tabulation, memoization https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net - 한 칸씩 넘어가면서 각 원소를 구간에 포함한 경우, 포함하지 않은 경우로 나눠서 최대합을 구하는 방식으로 풀었다. 어느 지점 i까지 구간에 포함하여 합을 구하였을 때 그 다음 구간에 추가하려면 i + 2부터 추가를 해야된다(구간이 연속되면 안된다) i 지점까지 사용한 구간의 갯수가 똑같다면 i + 2지점 이후로는 i지점까지 구한 최대합에 추가로 더해줘야하는 별개의 문제.. 2022. 6. 8.

티스토리툴바