인프런 커뮤니티 질문&답변

김태우

작성한 질문수

SW 역량테스트 합격하기 A형 with C++ (Advanced Algorithm)

원자 충돌 (코드트리, 2020 하반기 오전 2번)

안녕하세요 선생님 코드트리 원자충돌(2020 하반기 오전 2번)에서 질문 있습니다.

해결된 질문

작성

103

안녕하세요 선생님

원자 충돌(코드트리, 2020 하반기 오전 2번)에서 질문 있습니다.

처음에 짤때 낚시왕(BOJ 17143)을 떠올리고 아래 처럼 코드를 짰는데 오답이 나옵니다.

int dir=d;
int dist = s%n;
int sx = x;
int sy = y;
for(int cnt_k=0;cnt_k<dist;cnt_k++){
    int nx = sx+dx[dir];
    int ny = sy+dy[dir];

    if(nx<0) nx=n-1;
    if(nx>=n) nx=0;
    if(ny<0) ny=n-1;
    if(ny>=n) ny=0;

    sx = nx;
    sy = ny;
}

이 부분만 선생님의 코드로 바꾸면 문제가 없어서 이 부분이 틀린 것이 확실한데 왜 오답인지 모르겠습니다 ..

좋은 강의해주셔서 항상 감사드립니다 !.

c++코딩-테스트 소프트웨어-테스트 알고리즘

퀴즈

강의에서 소개된 A형 문제 풀이의 일반적인 접근 방식에 대한 설명으로 가장 적절한 것은 무엇일까요?

항상 가장 복잡한 알고리즘부터 적용해야 한다.

제공된 템플릿을 활용하여 입력 처리, 시뮬레이션 함수 등을 구조화한다.

문제의 작은 예시만 보고 풀이 방향을 결정한다.

디버깅 기능 사용 없이 한 번에 완벽한 코드를 작성한다.

답변 2

피로물든딸기

지식공유자

안녕하세요. 피로물든딸기 입니다.

보여주신 일부 코드는 원자를 1칸씩만 움직이는 것 같고, 좌표의 기준을 (0, 0)으로 잡으신 걸까요?

해당 내용으로는 크게 문제가 없어보입니다.

작성하신 전체 코드를 올려주시면, 다시 답변드리겠습니다!

제가 작성한 한 칸씩 이동한 코드는 잘 동작하는 것을 확인하였습니다.

		for (int i = 0; i < acnt; i++)
		{
			int nr, nc;
			int d, s, m;

			d = atom[i].d;
			s = atom[i].s;
			m = atom[i].m;

			int dist = s % N;
			int sr = atom[i].r;
			int sc = atom[i].c;

			nr = sr; nc = sc;
			for (int cnt_k = 0; cnt_k < dist; cnt_k++)
			{
				nr = sr + dr[d];
				nc = sc + dc[d];

				if (nr > N) nr = 1;
				if (nc > N) nc = 1;
				if (nr < 1) nr = N;
				if (nc < 1) nc = N;

				sr = nr;
				sc = nc;
			}

			// 2. 합성
			MAP[nr][nc].m += m;
			MAP[nr][nc].s += s;
			MAP[nr][nc].d = d;  // 원자가 1개인 경우 유효

			if (d % 2 == 0) MAP[nr][nc].even++;
			else MAP[nr][nc].odd++;

			MAP[nr][nc].count++;
		}

전체 코드는 다음과 같습니다.

#include <stdio.h>

#define MAX (50 + 5)

int T;
int N, M, K;

struct ATOM
{
	int r;
	int c;
	int m; // 질량
	int s; // 속력
	int d; // 방향
};

ATOM atom[100000 + 5000];
int acnt;

// ↑, ↗, →, ↘, ↓, ↙, ←, ↖
int dr[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

struct INFO
{
	int m; // 질량
	int s; // 속력
	int d; // 방향
	int even; // 상하좌우
	int odd; // 대각선
	int count; // 원자의 개수
};

void input()
{
	scanf("%d %d %d", &N, &M, &K);

	acnt = 0;
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d %d %d %d", &atom[acnt].r, &atom[acnt].c, &atom[acnt].m, &atom[acnt].s, &atom[acnt].d);
		acnt++;
	}
}

void printAtom() // for debug
{
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 0; i < acnt; i++)
		printf("%d %d %d %d %d", atom[acnt].r, atom[acnt].c, atom[acnt].m, atom[acnt].s, atom[acnt].d);
	putchar('\n');
}

void simulate()
{
	for (int k = 0; k < K; k++)
	{
		INFO MAP[MAX][MAX] = { 0 };

		// 1. 원자는 자신의 속력만큼 이동
		for (int i = 0; i < acnt; i++)
		{
			int nr, nc;
			int d, s, m;

			d = atom[i].d;
			s = atom[i].s;
			m = atom[i].m;

			int dist = s % N;
			int sr = atom[i].r;
			int sc = atom[i].c;

			nr = sr; nc = sc;
			for (int cnt_k = 0; cnt_k < dist; cnt_k++)
			{
				nr = sr + dr[d];
				nc = sc + dc[d];

				if (nr > N) nr = 1;
				if (nc > N) nc = 1;
				if (nr < 1) nr = N;
				if (nc < 1) nc = N;

				sr = nr;
				sc = nc;
			}

			// 2. 합성
			MAP[nr][nc].m += m;
			MAP[nr][nc].s += s;
			MAP[nr][nc].d = d;  // 원자가 1개인 경우 유효

			if (d % 2 == 0) MAP[nr][nc].even++;
			else MAP[nr][nc].odd++;

			MAP[nr][nc].count++;
		}

		// MAP을 보고 atom 배열 생성
		acnt = 0;
		for (int r = 1; r <= N; r++)
		{
			for (int c = 1; c <= N; c++)
			{
				if (MAP[r][c].count == 0) continue;

				if (MAP[r][c].count == 1)
				{
					atom[acnt].r = r;
					atom[acnt].c = c;
					atom[acnt].m = MAP[r][c].m;
					atom[acnt].s = MAP[r][c].s;
					atom[acnt++].d = MAP[r][c].d;

					continue;
				}

				// 2.d 질량이 0인 원자는 소멸
				if ((MAP[r][c].m / 5) == 0) continue;

				// 2.b 합쳐진 원자는 4개의 원자로 분해
				int dir[4] = { 0 };
				if (MAP[r][c].even == MAP[r][c].count
					|| MAP[r][c].odd == MAP[r][c].count)
				{
					dir[0] = 0;
					dir[1] = 2;
					dir[2] = 4;
					dir[3] = 6;
				}
				else
				{
					dir[0] = 1;
					dir[1] = 3;
					dir[2] = 5;
					dir[3] = 7;
				}

				for (int i = 0; i < 4; i++)
				{
					atom[acnt].r = r;
					atom[acnt].c = c;
					atom[acnt].m = MAP[r][c].m / 5; // 2.c.2
					atom[acnt].s = MAP[r][c].s / MAP[r][c].count; // 2.c.3
					atom[acnt++].d = dir[i];
				}
			}
		}
	}
}

int getAnswer()
{
	int sum = 0;
	for (int i = 0; i < acnt; i++)
		sum += atom[i].m;

	return sum;
}

int main()
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		simulate();

		printf("%d\n", getAnswer());
	}

	return 0;
}

감사합니다.

김태우

질문자

선생님이 짜주신 코드 보고 해결 했습니다 ! 감사드립니다 !!

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. ttt123님.

질문해주신 내용은 코드트리 원자 충돌 문제에서 발생한 오류에 대한 문의로 보입니다. 코드의 이동 부분에서 메커니즘이 제대로 작동하지 않는 것 같습니다. 낚시왕(BOJ 17143)과 유사하게 문제를 접근하셨지만, 이동하는 방식에서 오차가 발생한 것으로 보여요.

특히 주의해야 할 점은 다음과 같습니다:

Modular Arithmetic 사용: 이동하려는 거리 s를 격자 크기 n으로 나눈 s % n 값을 사용하셨습니다. 하지만 이 과정에서 경계 조건을 명확히 처리해야 합니다. 코드에서 사용하신 nx, ny의 범위를 초과했을 때 초과된 부분을 제대로 처리하지 못하고 있는 것 같습니다.
경계 처리: 격자를 벗어날 경우 다시 들어오는 위치를 정확히 계산해야 합니다. 코드에서 if(nx<0) nx=n-1;, 등을 통해 처리를 해주고 있는데, 이러한 부분이 예상대로 작동하지 않는 문제가 있을 수 있습니다.

아래는 문제와 관련된 링크를 제공합니다. 원자 충돌 문제와 관련된 직접적인 답변은 없지만 유사한 방향으로 접근할 수 있는 게시글을 추천드립니다:

문제 해결을 위한 일관성 있는 방식 찾기 - 여기서는 문제를 푸는 일관된 논리적 방식을 잡는 것이 중요하다고 설명하고 있습니다.

위 링크는 BOJ 성곽 문제에서의 논리적 접근에 대한 내용을 담고 있으며, 코드의 경계 처리 및 이동 로직을 재검토하는 힌트를 얻을 수 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

김태우

작성한 질문수

전체 Q&A

질문하기