잡다한 프로그래밍

https://swexpertacademy.com/main/main.do

1. 해결방법

먼저 배열에 N개의 수를 입력받고 이를 정렬한 후, 늘어나는 시간과 비교하며 M시간이 되면 빵을 K개만큼 추가하고, 만약 배열의 값을 cnt로 두고 배열[cnt] == 시간일 경우 빵의 개수가 0보다 같거나 작으면 불가, 크면 빵의 개수를 줄이고 cnt를 1씩 늘리고 time도 1 늘리는 방법으로 해결하려 하였다

2. 오류

그러나 배열내부에 배열[0] == 3 배열[1] == 3같이 같은 값이 들어가 있을 경우 시간은 이미 늘어나버려서 무한루프에 빠지는 현상이 발생하였고 while문을 2번 돌리는 방법으로 다음과 같이 해결하였다. 더 쉬운 방법도 존재하는 것 같으니 다른 블로그도 참고하길 바란다.

3. 코드

#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;

string result = "Possible";
int tmp[101];
    int test_case;
	int T;
    int N;
    int M;
    int K;

void check(){
    int time = 0;
    int cnt = 0;
    int bread = 0;
	while(1){
        if(cnt == N) {break;}
        if((time % M) == 0 && time != 0) bread += K;
        
        while(1){
        if(tmp[cnt] == time){
         if(bread <=0){
             result = "Impossible";
             goto EXIT;
         }
         else{
          bread--;
          cnt++;
         }
      
        	}else{
         break;   
        }
        }
        
        time++;
    }

    EXIT:
    return;
}

int main(int argc, char** argv)
{
	scanf("%d",&T);
	for(test_case = 1; test_case <= T; ++test_case)
	{
        scanf("%d %d %d",&N ,&M ,&K);
		
        for(int i = 0; i < N; i++){
            scanf("%d", &tmp[i]);
        }
    
		sort(tmp, tmp+N);
        result = "Possible";
       check();
        
        printf("#%d %s\n", test_case ,result.c_str());
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

링크

https://swexpertacademy.com/main/main.do

1. 해결방법

1. 첫번째 생각으로 bfs를 이용하여 각 위치를 들리며 최소 시간을 구하는 방법을 사용하였다

하지만 bfs방법은 시간이 너무 오래걸려 문제의 시간을 초과해버려서 다른방법을 생각해보아야했다.

2. bfs를 사용하는 방법이지만 queue를 사용하였고 또한 cin, cout 대신 scanf와 printf를 사용하였다 cin과 cout보다 scanf와 printf가 속도가 더 빠르다고 하여 사용하여 시간을 단축하였다.

2. 코드

1. bfs방법(실패)

#include <iostream>
using namespace std;
int total = 0;
int num = 0;
int ary[100][100] = {};
int temp = 9999;
bool bo[100][100] = { false };
int sum = 0;
int nx[4] = { 0, 0, -1, 1 };
int ny[4] = { -1, 1, 0, 0 };

void dfs(int x, int y, int val) {
	bo[x][y] = true;

	if (x == num - 1 && y == num - 1) {
		if (temp > val) {
			temp = val;
			bo[x][y] = false;
			return;
		}
	}
	else {
		for (int i = 0; i < 4; i++) {
			int dx = x + nx[i];
			int dy = y + ny[i];

			if (dx < 0 || dx >= num || dy < 0 || dy >= num || bo[dx][dy] == true) continue;
			dfs(dx, dy, val + ary[dx][dy]);
			bo[dx][dy] = false;
		}
	}

}

int main()
{
	scanf("%1d", &total);
	for (int i = 0; i < total; i++) {

		scanf("%1d", &num);
		for (int j = 0; j < num; j++) {
			for (int k = 0; k < num; k++) {
				scanf("%1d", &ary[j][k]);
			}
		}


		temp = 9999;
		fill(&bo[0][0], &bo[0][0] + sizeof(bo), false);

		dfs(0, 0, ary[0][0]);

		cout << "#" << i + 1 << " " << temp << endl;

	}
}

2. queue를 이용한 bfs방법

#include <stdio.h>
#include <queue>
#include <memory.h>


using namespace std;
int total , num;
int ary[100][100];
int temp[100][100];
bool bo[100][100];
struct Node {
	int x;
	int y;
    Node(int _x, int _y) {
        x = _x;
        y = _y;
    }
};
void bfs() {
	queue<Node> q;
	q.push(Node(0, 0));
	bo[0][0] = true;
int dx[] = { 1,-1,0,0 };
    int dy[] = { 0,0,1,-1 };
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			 int ax = x + dx[i];
            int ay = y + dy[i];
			if (ax < 0 || ay < 0 || ax >= num || ay >= num ) continue;
                if (!bo[ax][ay] || temp[ax][ay] > temp[x][y] + ary[ax][ay]) {
               temp[ax][ay] = temp[x][y] + ary[ax][ay];
                    q.push(Node(ax, ay));
                    bo[ax][ay] = true;   
             }
		}
	}

}
void init() {
	memset(temp, 0, sizeof(temp));
	memset(bo, false, sizeof(bo));
}
int main()
{
    scanf("%d", &total);
    for (int i = 1; i <= total; i++) {
		init();
    scanf("%d", &num);
        char buf[101];
        for (int j = 0; j < num; j++) {
            scanf("%s", &buf);
			for (int k = 0; k < num; k++) {
			ary[j][k] = buf[k] - '0';
            }
		}
		bfs();
        printf("#%d %d\n", i, temp[num - 1][num - 1]);
	}
}