문제를 처음 보고 정확하게 어떻게 풀어야 답이 나올지 정리를 못해서 계속 틀렸다 내가 생각한 방법은 무조건 숫자가 들어오면 계속 더해서 보관했다 그렇게하면 합치지 말아야 할 경우에 반례가 생긴다 방법은 작은 숫자부터 그리디하게 보면 해결된다 먼저 내가 받아온 숫자의 합이 n보다 작다면 -1이다 왜냐면 숫자를 계속 나눌수 있어서 1로 나눠서 다 합칠 경우에 어떤수든 성립 가능하다 만약 합이 더 클 때 Bit배열을 만들어서 계속 보관한다 그리고 n의 비트를 0번째부터 보면서 한번 답을 구해보자 만약 Bit[i]가 켜있다면 하나를 빼서 쓰면 된다 여기서 내가 캐치하지 못했던 부분이 있다 아래서부터 보기때문에 이제 더이상 Bit[i]는 필요없다 그래서 Bit[i+1]로 합쳐주면 된다 Bit[i+1] += Bit..
그리디로 풀 수있는 문제다 내가 움직일 수 있는 거리는 (손님 방문시간 - 현재시간)만큼이다 그럼 우린 시간순으로 정렬을하고 내가 움직일 수 있는 범위를 가지고 다니면서 만약 그 범위안에 손님이 만족하는 온도가 없다면 NO 가능하다면 YES를 출력해 줄 수 있따! 그리고 만족한다면 시간을 바꿔주고 왼쪽 오른쪽 범위는 각각 포함할 수 있는 최대, 최소의 거리로 해줘야한다 처음에는 만족하는 범위를 찾으려고 하다가 거꾸로 해야 쉽겠다 싶어서 주석처리하고 반대의 경우를 찾았다! 앞으로도 쉬운것좀 생각하자.. 어려운 방법말고..!! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 3..
주어지는 문자열들을 통해 만들수 있는 가장 긴 팰린드롬의 길이와 팰린드롬을 출력한다! 나는 map과 set을 이용해서 풀었다 먼저 set에 담는데 뒤집어서 같은 문자열이 있다며 팰린드롬의 짝이 된다 그래서 만약 뒤집어서 있다면 뒤집은 문자열의 카운트만 증가시켜주고 없다면 set에 넣어준다 그리고 set을 돌아보면서 각 문자열의 /2만큼은 기본적으로 붙일 수 있으므로 답에 추가하자! 그리고 만약 개수가 1인것중에 팰린드롬인것이 있다면 그것을 답의 중간에 붙여주자! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include using ..
이분탐색을 통해 값을 찾으려고했는데 계속 실패했다! 한번 생각해보자.. 이 문제에서는 인접한 수의 차를 최소로 하고싶고 그때의 k를 구하고싶다 그럴때는..! -1과 인접한 숫자들 중 최소와 최대의 평군이 최적이된다 문제를 풀면서는 생각못했는데 -1 옆에없는 수는 무시하는게 맞다 -1 옆에 있을때만 의미가 있으니까 근처에 있는 수를 찾아서 평균값을 구하고 대체해준다 그리고 n만큼 보면서 가장 큰 diff값을 찾으면 된다! ㅠㅠ 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include using namespace std; #define ll long long const int SIZE = 1e5+5; int..
dfs를 이용한 cycle 체크 문제 응용 만약 cycle이 있다면 NO이다 하지만 몇가지 조건이 더 있다 먼저 각 정점마다 최대 2개의 간선을 가지므로 indgree가 2보다 크면 fail 또한 cycle을 확인할 때 set을 통해 이미 본 간선은 지워준다고 생각하고 푼다 출력하는건 indgree가 낮은곳부터 쭉 dfs를 통해 출력하고 남은걸 출력하면 된다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67..
이분탐색으로 해결할 수 있는 문제다 mid일만큼 본다고 하면 mid/(g+b)만큼 g or b를 볼 수 있다 그럼 g*(mid/(g+b))만큼 좋은 날을 볼 수 있고 그 다음 볼수있는 날도 최대 g만큼 좋은날이다 결국 답은 g*(mid/(g+b))+min(mid/(g+b),g)로 나온다!! 근데 문제를 잘 보면 전체 도로를 어쨌든 공사는 해야하므로 최소 n일은 봐야한다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include #include using namespace std; #define ll long long ll n, g, b; bool solve(ll mid) {..