글 읽기 - 시간초과 관련해서 질문있습니다..

jokerkwu 4년 전 0

분명 로직이 똑같은거 같은데 하나는 통과되고 하나는 실패인데 어느부분에서 시간복잡도가 차이나는지 알 수 있을까요?

_{이 코드가 통과된 코드이고 밑에 코드가 시간초과난 코드입니다.}

_{사용된 반복문이 같고 로직이 같은데 어느부분에서 차이가 나는지 모르겠습니다.}

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

	const int MAX = 100 + 1;

	typedef struct
	{
	int y, x;
	}Dir;

	Dir moveDir[4] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} }; //N S E W

	int R, C, M;
	int arr[MAX][MAX];
	vector<pair<int, pair<int, int>>> shark[MAX][MAX];

	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> R >> C >> M;

	for (int i = 0; i < M; i++)
	{
	int r, c, s, d, z;
	cin >> r >> c >> s >> d >> z;

	shark[r][c].push_back({ z, {s, d - 1} });
	}

	int cur = 0;
	int result = 0;
	for (int c = 0; c < C; c++)
	{
	cur++;
	//땅에 제일 가까운 상어 먹고
	for(int i=1; i<=R; i++)
	if (shark[i][cur].size())
	{
	result += shark[i][cur][0].first;
	shark[i][cur].clear();
	break;
	}

	//r, c, z, s, d
	queue<pair<pair<int, int>, pair<int, pair<int, int>>>> q;
	for (int i = 1; i <= R; i++)
	for (int j = 1; j <= C; j++)
	if (shark[i][j].size())
	{
	q.push({ {i, j}, {shark[i][j][0]} });
	shark[i][j].clear();
	}

	//상어가 움직인다
	while (!q.empty())
	{
	int y = q.front().first.first;
	int x = q.front().first.second;
	int size = q.front().second.first;
	int speed = q.front().second.second.first;
	int dir = q.front().second.second.second;
	q.pop();

	for (int i = 0; i < speed; i++)
	{
	//위 아래
	if (dir == 0 \|\| dir == 1)
	{
	int next = y + moveDir[dir].y;
	if(!(1 <= next && next <= R))
	dir = 1 - dir;
	y += moveDir[dir].y;
	}
	//왼쪽 오른쪽ㄴ
	else
	{
	int next = x + moveDir[dir].x;
	if (!(1 <= next && next <= C))
	dir = 5 - dir;
	x += moveDir[dir].x;
	}
	}

	//이미 해당 칸에 상어가 있을 경우
	if (shark[y][x].size())
	{
	//해당 칸에 있는 상어 크기보다 자기가 더 클 경우에만 대체
	if (shark[y][x][0].first < size)
	{
	shark[y][x].clear();
	shark[y][x].push_back({ size,{ speed, dir } });
	}
	}
	//해당 칸에 상어가 없는 경우 바로 추가
	else
	shark[y][x].push_back({ size,{ speed, dir } });
	}
	}
	cout << result << "\n";
	return 0;
	}

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX 103
int R, C, M;

int m_xy[5][2] = { {0,0},{0,-1},{0,1},{1,0},{-1,0} };

typedef struct {
	int s;		//속도
	int d;		//방향
	int z;		//크기
}Info;

typedef struct {
	int c;		//x
	int r;		//y
}Point;

Info board[MAX][MAX];	//해당 위치에 상어 정보를 갖고 있는 변수
bool visited[MAX][MAX];	//해당 위치에 상어가 있는지 체크하는 변수
vector<pair<Point,Info>> sharks;	//좌표랑 상어 정보들

int find_shark(int x) {
	for (int i = 1; i <= R; i++) {
		if (visited[i][x]) {          
			visited[i][x] = false;
			return board[i][x].z;
		}
	}
	return 0;//러턴값을 제대로 안했더니 이상한 값 출력
}

int next_change_dir(int dir) {
	switch (dir) {
	case 1:
		return 2;
		break;
	case 2:
		return 1;
		break;
	case 3:
		return 4;
		break;
	case 4:
		return 3;
		break;
	}
}

void shark_move(pair<Point, Info> shark) {
	
	Point cur_pos = shark.first;
	Info cur_info = shark.second;
	Point next_pos=cur_pos;
	Info next_info=cur_info;

	//상어를 이동시키자
	for (int i = 0; i < cur_info.s; i++) {
		next_pos.c += m_xy[next_info.d][0];
		next_pos.r += m_xy[next_info.d][1];

		//범위를 벗어났는지 체크 벗어났다면 방향바꾸자
		if (next_pos.r == 0 || next_pos.c == 0 || next_pos.r > R || next_pos.c > C) {
			next_info.d = next_change_dir(next_info.d);
			next_pos.c += (m_xy[next_info.d][0]*2);
			next_pos.r += (m_xy[next_info.d][1]*2);
		}
	}


	//상어 이동 후 해당 좌표에 다른 상어가 있고 현재 상어가 더크다면  이 상어로 갱신.
	if (visited[next_pos.r][next_pos.c]&&board[next_pos.r][next_pos.c].z<next_info.z) {
		board[next_pos.r][next_pos.c] = next_info;
	}
	//해당 좌표에 상어가 없다면
	else if (!visited[next_pos.r][next_pos.c]) {
		visited[next_pos.r][next_pos.c] = true;
		board[next_pos.r][next_pos.c] = next_info;
	}


}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> R >> C >> M;
	for (int i = 0; i < M; i++) {
		Point pos;
		Info tmp;
		cin >> pos.r >> pos.c >> tmp.s >> tmp.d >> tmp.z;
		board[pos.r][pos.c] = tmp;
		visited[pos.r][pos.c] = true;
	}

	int res = 0;
	//1. 낚시왕 한칸씩 이동
	for (int i = 1; i <= C; i++) {
		//2. 땅에서 제일 가까운 상어를 찾는다.
		res += find_shark(i);
		//cout << i << "초 결과값 = " << res << '\n';
		
		
		//3. 상어들을 이동시킨다.
		
			// 3-1 칸에 상어가 있으면 벡터에 다 넣는다
		for (int y = 1; y <= R; y++) {
			for (int x = 1; x <= C; x++) {
				if (visited[y][x]) { 
					Point tmp = { x,y };
					sharks.push_back(make_pair(tmp,board[y][x]));
					visited[y][x] = false;
					board[y][x].z = 0;
				}
			}
		}
		
	
			//3-2 상어들을 하나씩 꺼내서 전부 이동시킨다.
		for (int s_i=0; s_i < sharks.size(); s_i++) {
			
			//이동시키자.
			shark_move(sharks[s_i]);

		}
		sharks.clear();
		
	}

	cout << res << '\n';
	return 0;
}

djm03178 4년 전 0

통과한 코드도 880ms나 됩니다. 시간 제한이 1초이니 시간 복잡도가 같더라도 효율성 측면에서 1.2배 정도만 차이나도 결과가 달라질 수 있다는 뜻입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 관련해서 질문있습니다..

jokerkwu 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말