본문 바로가기
백준 C++ 2234번 https://www.acmicpc.net/problem/2234 이 문제에서 비트가 켜져있으면 이동하면 안된다라는 점은 쉽게 알아낼 수 있었다.하지만 고민한 문제는 벽을 1개를 허문다는 점이었다.실제로 모든 칸에 대해서 한 비트씩 끄는 건 너무 비효율적이라고 생각했어서 다른 방법을 찾았어야했다.생각보다 방법은 쉽게 할 수 있었는데 visited로 구역을 나누는 것으로 했다. #include using namespace std;//성 방의 갯수 -> sectionNum - 1//가장 넓은 방의 넓이//하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기int n, m; int sectionSize = 0;int sectionNum = 0;int maxSectionSize = 0;int maxLink.. 2024. 5. 13.
백준 14890 C++ https://www.acmicpc.net/problem/14890이 문제는 조건이 까다롭지 하나하나 따지며 생각하면서 if문으로 뚫으면 괜찮다.실수한게 재귀함수에 return을 넣지 않아서 계속 result가 다르게 나와서 cout을 곳곳에 넣었는데 오히려 이 글을 보시는 분들이 출력을 잘 볼 수 있는 좋은 상황이 된거 같다. #include #include using namespace std;int n, l;int arr[101][101];int temp[101][101];int landCount = 0;int result = 0;void go(int y, int x, int past){ if (x >= n) { //끝까지 옴. //cout 1 || sub 0) { //현재가 더 높다. if.. 2024. 4. 27.
백준 2910 C++ https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 여기서 고민한 점은 결국 빈도수와 숫자가 가장 먼저 나온 index를 저장하는 방식이었다. set을 쓸까 고민도 했지만 map으로 진행하였다. map을 사용하는 방법에 대해서 잘 몰랐는데 덕분에 한번 알아보게 되었고 아래 코드에서 bin[t] == 0으로 확인하듯이 map에 값이 없으면 0으로 되어 있단 점을 이용해 이미 한번이라도 들어왔는지 확인을 하였다. #include #include #include #include using nam.. 2024. 4. 23.
백준 17471 C++ https://www.acmicpc.net/problem/17471 17471번: 게리맨더링선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.www.acmicpc.net 이 문제에서 비트마스킹을 어떻게 사용할지는 큰 고민을 하지 않았다.하지만 고민이 깊어진 것은 선거구가 모두 연결되어있는지? 이걸 어떻게 알것인가였다.처음에는 각 선거구를 vector로 저장해서 visited로 해당 선거구vector에 있는 요소가 다 들어왔는지 체크하려고 했다.아.. 근데 생각보다 복잡하게 코드가 흘러가서 파기하고 dfs로 돌며 모든 노드를 방문하였는지로 생각하였다. 결국 시작점이 0선거구 1선거구로 나눠.. 2024. 4. 17.
백준 14620 C++ https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net n이 결국 10x10이 최대라서 완전탐색하면 쉽게 풀 수 있는데 그저 DP를 할지 진짜 완전탐색을 할지 고민하다가 그냥 완전탐색으로 풀었다. #include #include using namespace std; int n;// 6 2024. 3. 25.
백준 9934 C++ https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 되게 이상한 규칙을 찾아서 재귀로 풀려고 했는데 틀렸다. #include #include #include using namespace std; /*처음에 상근이는 트리의 루트에 있다. 왼쪽을 먼저 방문한다. 그 다음 중앙 방문 오른쪽 방문 위로 이동 */ int k; // 1 2024. 3. 11.
백준 3197 C++ https://www.acmicpc.net/problem/3197 3197번: 백조의 호수입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.www.acmicpc.net 처음으로 플레를 혼자서 풀어서 성공했다. 처음에 그냥 일반적으로 빙판이 녹는걸 생각해서 시간초과가 나타났다.치즈와 같은 문제에서는 이렇게하면 풀렸기 때문이다.#include #include using namespace std;const int MAX = 1500;bool meet = false;int r, c;int dy[] = { -1, 0, 1, 0 };int dx[].. 2024. 3. 6.
백준 2529 C++ https://www.acmicpc.net/status?user_id=jjune0461&problem_id=2529&from_mine=1 채점 현황 www.acmicpc.net solved.ac 기준으로 실버인데 틀려서 자존심 상해서 다신 안틀리기 위해 복습... 일단 여기서 틀린 이유 to_string()의 존재를 생각 못함. char끼리 비교하면 되는데 char를 int로 바꿔서 하려다가 방법이 생각이 안나서 복잡하게 만듦. 제일 어이없는 건데 계속 다시 풀다가 전역변수와 main 함수 안에 변수를 동일한 걸 써서 찾지 못해 시간을 오래 잡아먹음. 일단 로직에 대해서 방문한건 방문처리하고 check함수는 잘 만들었다. 그저 비교하는 방식을 너무 꼬아서 생각해서 이렇게 실패했다. #include #in.. 2024. 3. 6.
백준 4179 C++ https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 이거 생각보다 어려웠습니다... 처음에 조금이라도 메모리를 절약해보겠다고 visited를 사용하지 않고 if문을 엄청 꼬아서 하니까 어디서 반례가 나타나는지 모르겠어서 그냥 visited를 만들어서 했습니다. 최단 거리니까 BFS를 사용했고 다양한 반례에 대해서는 한번 직접 생각하시면서 해보시는게 나을거 같습니다. #include #include using namespace std.. 2024. 2. 20.

티스토리툴바