[백준] 1463번 1로 만들기 (C++) - dynamic programming

문제

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

코드

#include <iostream>

using namespace std;

int arr[1000001];

int main(){
  int n;
  cin >> n;
  
  arr[2] = 1;
  arr[3] = 1; 
  for(int i=4; i<=n; i++){
    arr[i] = arr[i-1]+1;
    if(i%3 == 0 && arr[i/3]+1<arr[i]){
      arr[i] = arr[i/3]+1;
    }
    if(i%2 == 0 && arr[i/2]+1<arr[i]){
      arr[i] = arr[i/2]+1;
    }
  }
  
  cout << arr[n];
  
  return 0;
}

정리

처음에 arr을 main함수 안에 지역변수로 설정했더니 visual stuido code에서 코드가 실행되지 않았다. 그러나 전역변수로 설정했더니 잘 실행이 되었다. 왜 그런지 궁금해서 찾아보았다.

 

지역변수는 stack 영역에 할당되고 전역변수는 data 영역에 할당된다.

기본적으로 운영체제는 성능 상의 이유로 stack 영역에서 더 타이트하게 메모리 제한을 걸어버린다.

그래서 visual studio code에서 지역변수로 꽤 큰 용량의 변수를 선언하면 메모리 제한에 걸려 런타임 에러가 발생한다.

 

백준에서는 stack 영역에 별도의 메모리 제한이 존재하지 않아 지역변수에 꽤 큰 용량의 변수를 선언하여도 잘 실행이 된다. 그래도 내가 코드를 작성하는 곳은 vs code이기 때문에 웬만해서는 꽤 큰 용량의 변수면 전역변수로 선언해야겠다.

참조

https://www.acmicpc.net/board/view/64702

https://coding-insider.tistory.com/entry/%EC%A7%80%EC%97%AD%EB%B3%80%EC%88%98%EB%A1%9C-%ED%81%AC%EA%B8%B0%EA%B0%80-%ED%81%B0-%EB%B0%B0%EC%97%B4-%EC%84%A0%EC%96%B8-%EC%8B%9C-%EB%AC%B8%EC%A0%9C%EC%A0%90