c++ 5주차 알고리즘 스터디 숙제

아 저번주 숙제 다 못했다 현타온다 

한문제를 이틀씩 고민해도 안풀리는데 다들 어떻게 그렇게 척척 푸는지 신기할 따름이다 정말 

스터디시간에 각자 코드리뷰?간단하게 하는데 다들 너무 똑똑하다 퓨

스터디장님이 이번 주 숙제는 쉬운거로 내주셨는데 후다닥하고 못 푼 문제들 해봐야지 ㅠㅠ

이번 5주차에서는 투포인터를 배웠다.

저번에 한 번 공부했던 거라 추가적으로 개념공부는  안했다.

• A - 수들의 합 2
• B - 부분합
• C - 나이트의 이동
• D - 그림
• E - 보물
• F - 배열 돌리기 4  

 

백준 2003번 수들의 합2 (www.acmicpc.net/problem/2003)

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int arr[10005];
int main(void)
{
	int n, m , cnt=0;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		int num;
		scanf("%d", &num);
		arr[i] = arr[i - 1] + num;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			if (arr[j] - arr[i] > m) break;
			else if (arr[j] - arr[i-1] == m) {
				cnt++;
				break;
			}
		}
	}
	printf("%d", cnt);
}

매번 for 문 돌려서 계산하기 귀찮아서 배열을 누적합으로 입력하였다. 

 

 

백준 1806번 부분합(www.acmicpc.net/problem/1806)

#include<iostream>
#include<vector>
using namespace std;
vector<int> arr;
int main() {
	int n, m, number, temp;
	scanf("%d %d" , &n, &m);
	arr.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &number);
		arr[i] = arr[i - 1] + number;
	}
	int min_temp = n;
	if (arr[n] < m) cout << 0;
	else {
		for (int start = 1; start <= n; start++) {
			for (int end = start; end <= n; end++) {
				if (arr[end] - arr[start - 1] >= m) {
					temp = end - start + 1;
					if (temp < min_temp) min_temp = temp;
					break;
				}
			}
		}
		printf("%d" , min_temp);
	}
}

이것 또한 누적합으로 받아줬는데 arr[n]은 n개의 모든 수를 더한 것일텐데 arr[n]이 우리가 구해야할 m보다 작다면 뭘 더하든 m보다 크거나 같아질수가 없어서 이땐 그냥 계산도 안해버린다. 

 

근데 이게 진짜 웃긴 게 전에 풀었던 거 그대로 제출했는데 시간초과남 ;

뭐지 그럼 전에는 왜 맞은거야 운이 좋았던거냐구ㅜ

 

백준 7562번 나이트의 이동 (www.acmicpc.net/problem/7562) 

#include<iostream>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
int chess[305][305];
int dx[8] = { 1,2,2,1,-1,-2,-2,-1 };
int dy[8] = { 2,1,-1,-2,-2,-1,1,2 };

void bfs(int n, int start_x, int start_y, int end_x, int end_y) {
    queue<pair<int, int>>que;
    que.push({ start_x, start_y });
    chess[start_x][start_y] = 1;
    while (!que.empty()) {
        int x = que.front().first;
        int y = que.front().second;
        que.pop();
        if (x == end_x && y ==end_y) {
            printf("%d\n", chess[x][y] - 1);
            return;
        }
        for (int i = 0; i < 8; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx > -1 && nx<n && ny>-1 && ny < n && !chess[nx][ny]) {
                    chess[nx][ny] = chess[x][y] + 1;
                    que.push({ nx,ny });
            }
        }

    }
}

int main() {
    int testcase;
    scanf("%d", &testcase);
    for (int i = 0; i < testcase; i++) {
        int n, start_x, start_y, end_x, end_y;
        scanf("%d %d %d %d %d", &n, &start_x, &start_y, &end_x, &end_y);
        if (start_x == end_x && start_y == end_y) printf("0\n");
        else {
            memset(chess, 0, sizeof(chess));
            bfs(n, start_x, start_y, end_x, end_y);
        }
    }
}

이것도 최단 경로를 묻는 문제라서 무난하게 bfs로 풀었다.

특이한 점은 상하좌우가 아니라는 거 ....? 

그거만 빼면 기본 bfs 문제들이랑 다른 게 없는 거 같다. 

근데 자꾸 테스트 케이스 반복할떄마다 쓰레기값 쌓여서 1시간 넘게 고민했던 거 같은데

구냥 memset써서 해결됨,,,

 

백준 1026번 보물 (www.acmicpc.net/problem/1026)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>a;
vector<int>b;
int n;

int main() {
	scanf("%d", &n);
	a.resize(n);
	b.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		sum += b[n - i] * a[i - 1];
	}
	printf("%d", sum);
}

그냥 b를 기준으로 a를 재배열해서 같은 인덱스끼리 곱했을 때, 합이 제일 작은 것을 구해라 라는 문제인데,,,,

그냥 제일 큰 b 값에는 제일 작은 a 값을 곱하는 식으로 계산하면 된다.

엄청 간단하게 둘다 sort해서 b는 큰 순으로 a는 작은 순으로 곱하면 끝! 

 

백준 17406번 배열돌리기4(www.acmicpc.net/problem/17406)

아직 ㅎㅎ 고민해서 짰더니 pointer가 어쩌고 저쩌고 말이 많다 후