곧죽어도 콛잉

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 1) 구역을 2가지로 나누는 경우를 생각한다. 2) 1)에서 찾는 경우 중 같은 선거구끼리 인접시킬 수 있는지 확인한다. 3) 2)의 조건을 만족하는 경우 중, 두 개의 선거구 인구수의 차이가 최소가 되는 값을 찾는다. 어려웠다,,,, 생각하기 너무 힘들었던 것 같았다 dfs를 pair로 리턴해서 써먹는다면 좀 과정이 쉬워졌을 텐데 여러가지로 고생했다;; dfs 복습 필수..! 이 문제의 핵심 로직은 1) 우선 구역들..

https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 1) 0과 1로 이루어진 이진수라고 생각한다. 2) 모든 행을 뒤집는 경우를 백트래킹으로 찾아본다. 3) 각각의 경우의 수마다 뒤집어야할 열들을 찾아본다. 4) T의 개수가 최소가 되는 순간을 찾는다. 진짜 생각하는게 어렵다.......... 근데 감만잡으면 확실히 이해할 수 있다. 일단 문제를 이해해보자!! 딱 보면은 열과 행으로 나누어서 0번째 열부터 N-1번째 열까지, 각각의 열을 뒤집었..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 1) while(1)을 통해 계속해서 인구 이동을 체크하는 로직을 생각한다. 만약 인구이동이 발생됐다면, day++가 되고 그게 아니라면 종료하고 즉시 day를 출력한다. 2)모든 칸에 대한 인구이동을 dfs로 확인한다. 3)발생한 인구이동에 대한 연합의 인구수와 연합들의 위치를 저장하여, 평균을 구해 인구수를 맞춘다. 이때, 연합이 단 한개라면, 그 즉시 while문을 종료한다. ..

https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 1) 비트마스킹으로 식재료끼리의 조합을 구한다. 2) 구한 조합의 각각의 영양성분들끼리의 합이 최소 영양성분을 넘기는지 확인한다. 3) 최소 영양 성분을 넘긴다면, 이때의 비용과 식재료 조합을 vector에 저장한다. 4) vector을 sort로 오름차순 정렬하여 가장 첫번째 조합을 출력한다. 문제를 읽어보면 어? 이거 조합아닌가? 라는 생각이 든다. 하지만 조합으로 풀면 매우 어려운 선택이 ..

https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 1) 빈칸 중 3개를 뽑는 경우를 모두 찾는다. 2) 각 경우마다 씨앗을 심는다. 그리고 꽃이 폈을때(즉, 상하좌우를 확인할때) 조건에 맞는지 확인한다. 3) 만약 확인한 경우가 잘못됐다면, 다른 경우로 넘어가고, 아니라면 총 비용을 계산해서 최소값인지 확인한다. 이 문제는 전형적인 완전 탐색 문제이다! 이 문제의 시간복잡도는 아무리 커도 20만을 넘기지 않는다. (100 combination ..

https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 1) 0부터 9까지의 순열을 구한다. 2) 구한 순열의 모든 경우의 수를 부등호 사이에 넣어본다. 3) 2)에서 통과한 경우를, long으로 변환한 후 최소값인지 최대값인지 판별한다. 4) 모든 경우의수를 확인하면 최소값과 최대값을 출력한다. 진짜.. 쉬웠는데.. 헛짓거리를 많이했다... 문제 풀기전에 우리가 원하는 결과값의 데이터타입을 꼬오오오옥 확인하자 아무것도 모르고 atoi(s.c_str..