이것 저것 &

문제링크: https://www.acmicpc.net/problem/1022

구현문제였습니다.  회오리 모양으로 값이 증가하기에 구현하기 조금 까다로운 문제였습니다.

직관적으로 구현할때 흔히 할 수 있는 실수는 

1. 10001 * 10001 의 배열을 만들고 값들을 모두 저장한 후 결과를 도출하는 것입니다.

당연히 메모리 초과입니다.. 

2. 두번째 저지를 수 있는 실수는 재귀함수로 구현하는 것입니다.  5000번의 재귀가 호출하며 함수 호출과 매개변수 생성 등으로 시간초과를 가지게 됩니다. 

우선 정답 코드를 먼저 보여드리겠습니다. 

직관적이기 떄문에 쉽게 이해하실 수 있을거라고 생각합니다. 

#include <iostream>
#include <algorithm> // max 함수 사용
#include <cmath> // abs 함수 사용
using namespace std;

int r1, c1, r2, c2;
int map[50][5] = { 0 };
void solve() {
	int MAX = max(max(abs(r1), abs(c1)), max(abs(r2), abs(c2))); // max값을 찾는다.
	int val = 1; //소용돌이에서 값
	if (0 >= r1 && 0 >= c1 && 0 <= r2 && 0 <= c2)
		map[0 - r1][0 - c1] = val;

	int cnt = 0; // 현재의 카운트를 측정
	int y = 0, x = 0; // 좌표를 나타냄

	for (int i = 1; i <= MAX + 1; i++) {

		for (int i = 1; i <= 1 + cnt * 2; i++) {
			val++;
			x++;
			if (y >= r1 && x >= c1 && y <= r2 && x <= c2)
				map[y - r1][x - c1] = val;
		}
		for (int i = 1; i <= 1 + cnt * 2; i++) {
			val++;
			y--;
			if (y >= r1 && x >= c1 && y <= r2 && x <= c2)
				map[y - r1][x - c1] = val;
		}
		for (int i = 1; i <= 2 + cnt * 2; i++) {
			val++;
			x--;
			if (y >= r1 && x >= c1 && y <= r2 && x <= c2)
				map[y - r1][x - c1] = val;
		}
		for (int i = 1; i <= 2 + cnt * 2; i++) {
			val++;
			y++;
			if (y >= r1 && x >= c1 && y <= r2 && x <= c2)
				map[y - r1][x - c1] = val;
		}

		cnt++;
	}



}

int main() {
	cin >> r1 >> c1 >> r2 >> c2;
	solve();

	int h = abs(r2 - r1);
	int w = abs(c2 - c1);

	int MAX = 0;
	
	for (int i = 0; i <= h; i++) {
		for (int j = 0; j <= w; j++) {
			MAX = max(MAX, map[i][j]);
		}
	}
	
	//int MAX = max(max(map[0][0], map[0][w - 1]), max(map[h - 1][0], map[h - 1][w - 1])  ); // max값을 찾는다.
	int max_degree = 0;
	for (int i = 1; i <= MAX; i *= 10) {
		max_degree++;
	}
	for (int i = 0; i <= h; i++) {
		for (int j = 0; j <= w; j++) {
			int current_degree = 0;
			for (int k = 1; k <= map[i][j]; k *= 10)
				current_degree++;
			for (int k = current_degree; k < max_degree; k++)
				cout << ' ';

			cout << map[i][j] << ' ';
		}
		cout << '\n';
	}

}

solve함수에서 회오리로 이동하는 값들을 계산하면 반복문을 실행하고, 만약 (r1,c1)과 (r2,c2) 값 사이에 있다면 배열에 저장합니다.

그 이후에는 반복문을 통해 최대값의 자릿수를  max_degree에 저장하고 모든 값의 자릿수를 max_degree에 맞춰 적절히 공백을 넣어주면 됩니다. 

막상 짜고나면 간단해보이지만 코딩할 때는 어려운게 정석인 문제...

좀 더 효율적인 방법이 많을거 같아서 코드를 찾아봤습니다.

#include<cstdio>
int a[50][50], r1, c1, r2, c2, m, s;
int main() {
	scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
	for (int i = r1; i <= r2; i++) {
		for (int j = c1; j <= c2; j++) {
			int x = i - r1, y = j - c1;
			if (i - j < 0) {
				if (i + j < 0) a[x][y] = 4 * i*i + i + 1 - j;
				else a[x][y] = 4 * j*j - 3 * j + 1 - i;
			}
			else {
				if (i + j < 0) a[x][y] = 4 * j*j - j + 1 + i;
				else a[x][y] = 4 * i*i + 3 * i + 1 + j;
			}
			if (a[x][y] > m) m = a[x][y];
		}
	}
	for (; m; m /= 10) s++;
	for (int i = 0; i <= r2 - r1; i++) {
		for (int j = 0; j <= c2 - c1; j++) printf("%*d ", s, a[i][j]);
		puts("");
	}
	return 0;
}

너무 간결하게 예쁜코드네요.

애초에 회오리가 규칙있게 값이 증가하기에 경우마다 값을 계산해서 O(200)만에 해결한 방법입니다. 

저렇게 짤 수 있으면 정말 잘하시는거겠지만 좋은 코드의 조건을 여러가지가 있을 수 있습니다.

어떤 사람에게는 직관적이고 이해하기 쉬운 코드일수도, 다른 사람에게는 짧고 시간이 짧게 드는 것일 수도 있습니다.

사람마다 기준이 다르기에 어떤게 옳다고 볼 수는 없습니다. 

꼭 직접 보지않고 구현해보세요. 구현문제의 핵심은 연습입니다.

화이팅 :) 

문제링크:https://www.acmicpc.net/problem/5567

구현문제입니다.

문제가 직관적이기 때문에 구현에 어려움은 없으실겁니다.

제가 고민했던 문제는 실행시간입니다.

m<= 10000 이기때문에  m을 입력받고 O(m*m)인 이중포문으로 구현하게 되면 O(100,000,000)으로 1억번 실행되기에 1초에 딱맞습니다. 그래서 시간초과가 날까 걱정했습니다.

#include <iostream>
using namespace std;
int n = 0, m = 0, result = 0;
bool visited[501] = { 0 };
int arr[10000][2] = { 0 };
int main() {
	cin >> n >> m;

	for (int i = 0; i < m; i++) 
		cin >> arr[i][0] >> arr[i][1];

	for (int i = 0; i < m; i++) {
		if (arr[i][0] == 1) { //상근이의 친구
			int val = arr[i][1];
			visited[val] = 1; //체크
			for (int j = 0; j < m; j++) {// 상근이 친구의 친구들도 체크
				if (arr[j][0] == val)
					visited[arr[j][1]] = 1;
				else if (arr[j][1] == val)
					visited[arr[j][0]] = 1;
			}
		}
	}

	for (int i = 1; i <= n; i++)
		if (visited[i] == 1) {
			result++;
			
		}
	cout << result - 1 << endl;
}

다행히 ac를 받았습니다.

시간도 얼마걸리지 않았습니다. ( 아마 테스트케이스에 극단값이 없을 수 있기 때문에 )

구현문제는 항상 좀더 컴팩트한 답을 생각하셔야 합니다.

#include <cstdio>
int main(){
    int n,m,a,b,ans=0;
    short int arr[501][501]={0,};
    scanf("%d%d",&n,&m);
    for(int i =0 ; i<m; i++)
        scanf("%d%d",&a,&b),arr[a][b] = 1,arr[b][a] = 1;
    for(int i=2; i<=n; i++){
        if(arr[1][i] ==1){
            ans++;
        }
        else{
            for(int j = 1; j<=n; j++){
                if(arr[i][j] == 1 && arr[j][1] == 1){
                    ans++;break;
                }}}}
    printf("%d\n",ans);
}

위 처럼 그래프에 값들을 저장하고 O(n*n)으로 계산할 수 있었습니다.

실행시간도 훨씬 적고 정작 배열의 크기도 작아 메모리도 더 적게 드는 답안이었습니다.

화이팅 :) 

문제링크: https://www.acmicpc.net/problem/2851

구현문제입니다. 단순히 반복되는 값들에서 100에 가까운 만큼 더해주면 되는 쉬운문제였습니다.

별다른 설명없이 정답코드입니다.

#include <iostream>
#include <cmath>
using namespace std;

int arr[10] = { 0 };
int sum = 0; 
int main() {
	for (int i = 0; i < 10; i++) 
		cin >> arr[i];

	for (int i = 0; i < 10; i++) {

		if (abs(100 - sum) >= abs(100 - (sum + arr[i])))
			sum += arr[i];
		else
			break;
	}
	cout << sum << endl;
}

위처럼 구현해주시면 됩니다. :) 

문제링크: https://www.acmicpc.net/problem/8979

쉬운 구현문제입니다.

1. 금메달 수가 더 많은 나라 
2. 금메달 수가 같으면, 은메달 수가 더 많은 나라
3. 금, 은메달 수가 모두 같으면, 동메달 수가 더 많은 나라 

위의 기준으로 배열을 정렬하고 같은 순위인 나라의 갯수를 세어준 후 빼주면 되는 쉬운 문제였습니다.

C++의 sort함수가 익숙하지 않으신분들은  아래 포스팅을 참고해주세요

https://gusdnr69.tistory.com/52?category=765773

정답코드입니다. 

#include <iostream>
#include <algorithm>
using namespace std;

struct country {
	int country_number;
	int gold;
	int sliver;
	int bronze;

};

bool cmp(country a, country b) {
	if (a.gold > b.gold) return true;
	else if (a.gold == b.gold) {
		if (a.sliver > b.sliver) return true;
		if (a.sliver == b.sliver) {
			if (a.bronze > b.bronze) return true;
		}
	}

	return false;
}

country arr[1001];
int n, k;
int n1, n2, n3, n4;
int result = 0,val=0;

int main() {
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		cin >> n1 >> n2 >> n3 >> n4;
		arr[i].country_number = n1;
		arr[i].gold = n2;
		arr[i].sliver = n3;
		arr[i].bronze = n4;
	}

	sort(arr, arr + n, cmp);

	for (int i = 0; i < n; i++) {
		if (arr[i].country_number == k) {
			result = i;
			break;
		}
	}
	for (int i = result - 1;; i--) {
		if (arr[i].gold != arr[result].gold || arr[i].sliver != arr[result].sliver || arr[i].bronze != arr[result].bronze) {
			break;
		}
		val++;
	}
	cout << result - val + 1 << endl;
}

구조체를 통해서 구현을 했습니다. 

천천히 보시고 꼭 직접 구현해보세요! 

화이팅 :)

문제링크:https://www.acmicpc.net/problem/1748

전형적인 구현문제입니다. 

다만 n이 최대 1억번까지이기에 구현방법에 대해서 조금 생각해봐야했습니다.

저는 그냥 일반적인 논리로 접근했습니다.

#include <iostream>
using namespace std;
int n = 0, result = 0;

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		if (i <= 9)
			result += 1;
		else if (i <= 99)
			result += 2;
		else if (i <= 999)
			result += 3;
		else if (i <= 9999)
			result += 4;
		else if (i <= 99999)
			result += 5;
		else if (i <= 999999)
			result += 6;
		else if (i <= 9999999)
			result += 7;
		else if (i <= 99999999)
			result += 8;
		else
			result += 9;
	}
	cout << result << endl;
}

네 당연히 ac입니다.

하지만 조금 더 효율적인 코드를 찾아봤습니다.

#include<cstdio>
int n, r;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i *= 10) 
		r += n - i + 1;
    printf("%d", r);
    return 0;
}

크으 ... 아름다운 코드...

위 코드의 핵심은 매번 반복문마다 1의자리수의 합을 더해주고, 다음 반복문에서는 2의 자리수의 합을 더해준다는 개념입니다. 

대략 120정도의 값을 대입해보시면 이해가 가실겁니다.

이렇게 구현문제는 풀어보는 것이 끝이 아니라 다른사람의 효율적인 코드를 보는게 더욱 도움이 된다고 생각합니다.

화이팅 :)