loltochess

숫자 N을 연속된 자연수의 합으로 나타낼 수 있는 가지수를 출력하는 문제이다.예를 들어 숫자 5는 2+3, 5로 나타낼 수 있고 숫자 7은 3+4, 7로 나타낼 수 있다. 문제해결방법1.start와 end를 시작점에 위치시킨다.2.만약 구간의 합이 N보다 작다면 end를 ++하고 N보다 크다면 start를 ++한다.3.start가 end보다 커지면 종료한다. sum==N과 같아졌을 때 end를 움직여도 되고 start를 움직여도 된다. 각각 알맞게 코드만 작성해주면 된다. #include using namespace std;int main(void){ int N = 0; cin >> N; int start = 1; int end = 1; int count = 0; int sum = 1; while (st..

이 문제는 N이 1024 이하 M이 10만까지 입력받을 수 있다.만약 x1, y1, x2, y2를 입력받고 케이스마다 일일이 계산을 하면 최악의 경우의 수로 10만*10만까지 갈 수도 있다. 그래서 배열을 입력받을 때 미리 합을 누적해야 한다.(arr [i][j] += arr[i][j - 1]) x1, y1, x2, y2으로 2,2,3,4,를 입력받으면 3+4+5+4+5+6의 값을 출력하면 된다.문제에서 조건으로 x1x1의 행에서 x2의 행까지 y1의 열부터 y2의 열까지의 합을 계산하면 된다.for (int i = x1; i 즉 이런 식으로 더하겠다는 의미이다. 이 문제는 출력값이 많기 때문에 출력으로 인한 시간초과를 방지하기 위해ios::sync_with_stdio(false); cin.tie(NUL..

수가 주어졌을 때 i번째 수부터 j번째 수까지 합을 구하는 문제이다.입력으로 N과 M이 10만까지 주어지기 때문에 O(n^2)으로는 문제를 해결할 수 없다.매번 더하는 방식으로는 문제를 해결하지 못한다. 그럼 어떻게 해결을 해야 하는 것인가?미리 더해놓음으로써 매번 더하는 작업을 없앨 수 있다. (arr[i]+=arr[i-1]) 입력을 받는 동시에 미리 더한다.5 9 12 14 15이렇게 더한 후 만약 2 3 이 입력으로 들어오면 2 이전에 값은 필요가 없어지니 12-5=7을 출력하면 된다.i부터 j까지의 합을 얻으려면 i 이전에 값을 제거해 주는 작업이 꼭 필요하다. (arr[j]-arr[i-1]) 그리고 출력하는 작업이 많다 보니 출력으로 인한 시간초과를 피하기 위해 ios::sync_with_std..

암호는 정렬된 문자열로 되어있고 최소 한 개의 모음과 두 개 이상의 자음으로 구성되어 있다. 문제해결방법1. 문자의 종류 C를 입력받은 후 정렬한다.2. 정렬된 데이터를 바탕으로 조합을 만든다.(DFS)3. 완성된 조합이 한 개 이상의 모음과 두 개 이상의 자음을 가지고 있으면 출력한다. #include #include using namespace std;char arr[16];int visited[16];char result[16];void DFS(int start, int num1, int num2, int count);int L = 0;int C = 0;int main(void){ cin >> L >> C; for (int i = 0; i > arr[i]; } sort(arr, arr + C); D..

#include #include using namespace std;long long visited[1000001];int main(void){ long long T = 0; cin >> T; for (long long i = 0; i > k; long long count = 0; priority_queue> pq1; priority_queue> pq2; for (long long j = 0; j > c >> num; if (c == 'I') { pq1.push({ num,j }); pq2.push({ -num,j }); count++; } else if (c == 'D') { if (num == 1) { if (count > 0) { ..

우선 입력으로 20만까지 들어오고 공유기의 개수도 2 어떻게 하면 시간복잡도를 줄일 수 있을까?이 문제는 이분탐색을 활용하는 문제이다.근데 이 문제는 특이하게 거리를 기준으로 이분탐색을 진행한다. 그래서 좀 헷갈렸던 거 같다.거리를 기준으로 이분탐색을 한다는 말이 뭐냐면 만약 입력으로 1 2 4 8 9가 들어왔다고 치자.그러면 가장 먼 거리는 (9-1)이고 가장 적은 거리는 (2-1)이다. 1과 8 이 거리 정보를 가지고 문제를 접근해야 한다. 두 집의 거리의 차이는 적어도 0보다는 크기 때문에 L을 1로 두고두 집의 거리의 차이는 적어도 9보다는 작기 때문에 R을 8로 둔다.L과 R의 합을 2로 나눈 값부터 확인해 나간다. (L+R)/2(1+8)/2=4먼저 거리 4부터 확인한다.먼저 처음에 기준으로 잡..

자기 최고점을 가지고 평균을 다시 내는 문제이다. (과목점수/최고점)*100 문제풀이방법1. 배열에 과목별 점수를 저장한다.(저장하면서 최고점을 구함.) //최고점은 double로 저장2. 모든 과목의 점수를 다시 계산해서 sum에 누적한다.3. sum을 과목 수만큼 나눠준다.  #include using namespace std;int arr[1001];int main(void){ int N = 0; cin >> N; double max = 0; for (int i = 0; i > arr[i]; if (arr[i] > max) { max = arr[i]; } } double sum = 0; for (int i = 0; i

이 문제는 공백 없이 숫자가 주어졌을 때 그 합을 구하는 문제이다. 문제풀이방법1. 숫자를 공백없이 입력받으라고 했으니 string으로 입력받는다.2. 0부터 N-1까지 string에 index로 접근해서 값을 구한다. 이때 구해지는 값은 문자형태(char)로 반환되기 때문에 -48을 하거나 -'0'을 해줘야 한다.3. sum에 구한 값을 누적해 준다. string a="123";stoi(a) //string을 int로 형변환string b="123.123"stof(b) //string을 float로 형변환 #include #include using namespace std;int main(void){ int N = 0; string s = ""; cin >> N >> s; int sum = 0; for..

이분탐색 문제이다. 뭔가 문제를 읽었을 때는 모든 경우의 수를 확인해서 값을 확인해야 할 거 같지만 그렇지 않다.시간 복잡도를 O(n^2) 미만으로 문제를 풀어야 한다. 처음에 문제를 보고 이분탐색을 사용해야 한다고 생각하기는 했는데 음수와 양수를 나눠서 양수의 데이터 하나를 음수로 가지고 간 후 이분탐색을 해서 가장 가까운 데이터를 찾는 방법으로 문제를 접근하려다가 실패했다.너무 어렵게 생각을 하지 말고 특성값이 0에 가장 가까운 용액을 만드는 경우가 두 가지 이상이면 그중 아무것이나 하나 출력하면 된다는 것에 집중을 하자. 문제풀이방법1. 배열을 일단 정렬한다.2. 배열의 arr [0] 값을 start로 두고 arr [N-1]를 end로 둔다.3. arr [start] 값과 arr [end] 값을 더..

걷거나 순간이동해서 가장 빠르게 동생의 위치를 찾는 방법이 몇 가지인지 찾는 문제이다. 이 문제는 가장 빠른 시간 안에 이동하는 문제이기 때문에 BFS를 사용할 수 있다.이런 식으로 BFS를 통해서 모든 경우의 수를 탐색해 주면 최단시간을 구할 수 있다. 그런데 여기서 정말로 모든 경우의 수를 계산하게 된다면 너무 많은 경우의 수가 존재해서 메모리 초과가 발생한다. 그래서 visited라는 배열을 둬서 이미 방문한 곳은 다시 방문하지 않게 하는 게 이 문제의 핵심이다. 만약 시간이 0초이고 시작 지점이 1이라고 생각을 해보자. 동생이 만약 4에 있다면 1 2 4가 가장 빠른 경로이다.1에서 2로 가는 경우의 수는 2가지가 있다. (걸어서 가거나 순간이동해서 가거나)위 2가지는 다른 방법이다. 그래서 시간..