알고리즘/BOJ 썸네일형 리스트형 1107번 1107번 - 리모컨 처음에 어떻게 풀어야할까 고민을 많이 했다. 완전 탐색이란 걸 알았는데도, 어떤 식으로 구현할지 몰랐다. 그러다가 일단, 두가지 케이스로 생각했다. 첫번째, +와 - 만을 이용해서 움직이는 경우.두번째, 특정숫자로 간 후, +와-만을 이용해서 움직이는 경우. 하지만 특정 숫자로 어떻게 가야할지에 대해서 감이 잡히지가 않았다. 그러던 중 내가 숫자로 가기 보다는 그 목적 숫자를 +1, -1 하면서 갈 수 있는 가장 빠른 경우 ( 그래야 특정 숫자로 이동 후, +와 - 연산을 최소화 할 수 있다.) 를 찾고 그 이후에 그 숫자의 자릿수를 더해주면 된다고 생각했다. x는 목적지 기준으로 - 를 해주고, y는 목적지를 기준으로 +를 해주면서 가장 가까운 값을 찾았다. 만약 리모컨의 모든 숫.. 더보기 1476번 1476번 - 날짜 계산 완전 탐색 1234567891011121314151617181920212223242526272829303132#include using namespace std; int main(){ int E, S, M; cin >> E >> S >> M; int e = 1, s = 1, m = 1; int year = 1; while (e != E || s != S || m != M) { e++, s++, m++, year++; if (e == 16) { e = 1; } if (s == 29) { s = 1; } if (m == 20) { m = 1; } } cout 더보기 11399번 11399번 - ATM 그리디 알고리즘으로 줄을 어떻게 세울지 결정하는 문제이다. 시간이 가장 적게 걸리는 순으로 짜면 된다. i 번째 사람이 걸리는 시간을 T[i] 라고 하면 T[1]=P[1]T[2]=P[1]+P[2]T[3]=P[1]+P[2]+P[3].....T[i]=P[1]+P[2]+P[3]+....+P[i] 가 된다. 그래서 T 의 전체 합이 최소로 만들기 위해서는 가장 많이 중복되는 수가 가장 적은 수가 되어야 한다. 그래서 그냥 sort를 통해 오름차순으로 정렬하고 합을 구했다. 증명) 시간이 가장 적게 걸리는 사람 순이 아닌 최적의 답이 있다고 가정해보자. 그게 A B C 라고 해보자. 그리고 시간이 가장 적게 걸리는 사람 순으로 세운 답이 B C A 라고 해보자. 그러면 B N; for (i.. 더보기 1931번 1931번 - 회의실 배정 그리디 알고리즘에서 가장 대표적인 문제. 가장 빨리 끝나는 회의를 가장 먼저 시작하면 된다. ##알게된 점## vector 가 sort 함수를 썼을 때 어떻게 될지 궁금했는데, first에 대해서 오름차순, 그리고 같은 first 값은 second 값에 따라 오름차순으로 정렬이 됐다. (뭐 당연한 얘기지만 확인 사살) 처음에 v.resize(n+1)을 해줘서 정렬할 때, 입력하지 않은 수 (0,0) 까지 정렬되었다... 이런거 조심하자. 12345678910111213141516171819202122232425262728293031323334353637383940#include#include#includeusing namespace std; int main(){ int n, a.. 더보기 1744번 1744번 - 수 묶기 수를 묶어서 최대값을 구하는 문제. 나는 양의 수, 0과 음의 수를 나누어서 vector 에 저장하였다. 양의 수는 내림차순으로, 음과 0의 수는 오름차순으로 sorting 하였다. 양의 수는 큰수끼리 곱할 수록 커지고, 음수는 작은 수끼리 곱할 수록 커지기 때문이다. 곱하다가 남는 값은 그냥 더해주는 방식으로 처리했다. 근데 처음에 예외를 찾지 못했다. 양수를 곱할 때, 둘 중 하나라도 그 수가 1이라면, 곱하기 보다는 더하는게 나을 수 있기 때문이다. 예를 들어 수열에 1 ,2 가 있다면 1*2 =2 이지만, 1+2 = 3으로 더하는 값이 더 크다. 그래서 양의 수를 곱할 때 for문 안에서 예외처리를 해서 AC를 받을 수 있었다. 1234567891011121314151617.. 더보기 1783번 1783번 - 병든 나이트 이 문제는 어떤 규칙? 어떤 범위를 나눠서 풀 것인가에 대해서는, 푸는 방법을 알았다. 그런데 뭔가 어떤식으로 코드를 일반화를 시켜야 할지, 그게 부족해서 case를 모두 나눠서 풀었다.. N이 3이상이고 M이 7 이상일 때는 답이 M-2 가 나온다는 사실을 알았는데 구현에서 문제가 발생했다. 일단 이 나이트는 무조건 오른쪽으로 움직이게 된다, 따라서 똑같은 자리를 다시 방문할 일이 없기 때문에 생각하기가 쉽다. 처음에는 숫자가 너무 큰데 겹치는 경우가 발생하면 어떡하지 하다가 겹치지 않는다는 사실을 알았다. 그래서 오른쪽으로 2칸 이동하는 2가지 방법을 빼고, 1칸씩 이동하는 것을 썼을 때 최대로 방문횟수가 나오게 된다. 근데 4번 이상에서는 모두 써야 한다는 점에서 다양한 .. 더보기 10610번 10610번 - 30 N의 범위가 너무 커서 string을 통해 문자열로 입력을 받았다. 그리고 이 각 문자열을 int 형으로 변환해서 vector 에 담았다. 30=2 * 3 * 5 이기 때문에 30의 배수이기 위해서는 3의 배수이자, 2의 배수이자 , 5의 배수여야 한다. 따라서 나는 3의 배수이자 2*5=10 의 배수를 찾기로 하였다. (조건 2개) 10의 배수이기 위해서는 끝자리에 0이 하나만 있으면 된다. (조건 1개 해결) 3의 배수이기 위해서는 각 자리의 합이 3의 배수여야 한다.(조건 2개 해결) - 증명은 구글링 이 조건에 맞게 가장 큰 정답을 구하기 위해서, 구한 각 자리를 내림 차순으로 정렬할 필요가 있었다.( sort 후에 reverse 를 이용함) 그리고 check 에는 각 자리의.. 더보기 2875번 2875번 - 대회 or 인턴 문제 분류에 그리디 알고리즘인데.. 그리디 알고리즘이 맞는지 모르겠다 내가 푼 방식이.. 나는 우선 주어진 N,M에서 가장 많이 만들 수 있는 팀의 수를 만들었다. 여자와 남자 비율이 2:1로 팀을 이루어야 하기 때문에, 모든 남자를 팀에 속할 경우는 N>=2*M 보다 커야 팀이 M개가 생기게 된다. 반대로 N> N >> M >> K; int left = 0; int team = 0; if (N >= 2 * M) { left = N - 2 * M; team = M; } else { if (N % 2 == 0) { left = M - (N / 2); team = N / 2; } else { left = M - (N / 2) + 1; team = N / 2; } } while .. 더보기 이전 1 ··· 27 28 29 30 31 32 33 ··· 40 다음