글 읽기 - 이 코드가 멀쩡히 돌아가는 이유???

puyopuyo 1년 전 0

일단 끄적이고 봤는데 이상한점이..

1. algorithm 헤더가 없는데 13행 fill에서 컴파일에러가 발생하지 않는 이유?

2. 17행에서 i가 1000000일 경우, dp[1000001]을 접근하게 되는데 이 때 OutofBounds가 뜨지 않는 이유? -> 힙과 연관?

두 가지가 궁금하네요

#include <iostream>
#define INF 987654321

using namespace std;

int N;
int dp[1000001];

int main() {

	cin >> N;
	
	fill(dp, dp + 1000001, INF);
	dp[1] = 0;

	for (int i = 1; i <= N; i++) {
		dp[i + 1] = min(dp[i] + 1, dp[i + 1]);
		if (i * 2 <= 1000000)
			dp[i * 2] = min(dp[i] + 1, dp[i * 2]);
		if (i * 3 <= 1000000)
			dp[i * 3] = min(dp[i] + 1, dp[i * 3]);
	}

	cout << dp[N];

	return 0;
}

fblood53 1년 전 0

C/C++은 배열 이름이 첫번째 원소에 대한 주소값이고 할당한 자료형에 따라 다음 주소에 차례대로 할당이 됩니다. 첫번째 원소의 주소가 1이라고 하고 int 형 메모리를 4라고 할때 1, 1+4, 1+4+4 ...... 이런식으로 가죠

따라서 배열을 넘어서 접근은 가능합니다. 대신 그곳에 어떤 값이 이미 할당되어있을 수도 있고 그냥 쓰레기값이 들어있을 수 있는 지는 미지수죠

C/C++이 어려운 이유가 이런 부분에서 컴파일 에러를 내보내지 않아 버그를 찾기가 어려울 수 있습니다.

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

문제

문제

출처

ICPC

이 코드가 멀쩡히 돌아가는 이유???

puyopuyo 1년 전 0

fblood53 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말