본문 바로가기

백준31

원티드 쇼미더코드 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 11559 - Puyo Puyo(DFS, BFS, 배열 조작, 구현) C++, Java 풀이 https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net - 전형적인 구현 문제이지만 생각보다 정확하고 빠르게 풀기 힘들었던 문제이다. 한 턴에 연쇄가 여러 번 일어나도 1연쇄로 카운트 되므로 한 턴에 모든 연쇄에 대해서 처리한 다음 블럭을 아래로 내리면 된다. C++은 dfs, Java는 bfs로 풀이하였다. #include #include #include #include #include using namespace std; .. 2022. 3. 23.

티스토리툴바