dfs(int day) 함수는 day번째 날 부터 최대 벌 수 있는 돈의 양을 리턴하게 된다.
각각의 경우 상담을 하거나 / 하지 않거나의 두가지 선택지가 있는데,
상담을 할 시, 상담 완료 기간만큼 시간이 지나고, 상담해서 받을 수 있는 금액을 얻게 된다.
상담을 하지 않을 시, 금액을 얻지 못하지만, 곧바로 다음 날 있는 상담을 선택할 지 말지를 결정할 수 있게 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T[20], P[20];
int N;
int dfs(int day) { //day번째 날 부터 벌 수 있는 최대 돈
if (day >= N) return 0;
int ret = 0;
if (T[day] + day <= N) {
ret = max(ret, dfs(day + T[day]) + P[day]);
}
if (day + 1 < N)
ret = max(ret, dfs(day + 1));
return ret;
}
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> T[i] >> P[i];
}
cout << dfs(0) << endl;
}
32비트, 64비트 하는 것은 워드 사이즈를 말하는 것입니다. 32비트 머신(CPU)라면 그 머신의 기본 데이터 처리 단위는 32비트가 되고, 64비트 머신이면 그 머신의 기본 데이터 처리 단위는 64비트가 되는 것입니다.
비트는 정보 처리의 단위니깐, 당연히 64비트 머신은 32비트 머신보다 한번에 처리할 수 있는 데이터의 크기가 2배가 되겠지요?
가능한 CPU와 운영체제 조합
32비트 64비트가 CPU에도 있고 운영체제에도 있습니다. 이분법적으로 나누어 생각해보면, 컴퓨터 시스템은 하드웨어와 소프트웨어가 있죠.
CPU는 하드웨어가 될 것이고, 운영체제는 소프트웨어가 됩니다.
그리고 CPU에 32비트, 64비트가 있고 운영체제에도 32비트, 64비트가 있는데 각자 HW / SW이므로 총 4가지 조합이 있을 수 있겠지요? 다음과 같이말입니다.
CPU
운영체제
가능여부
동작
32bit
32bit
O
32bit
64bit
X
불가능
64bit
32bit
O
32bit (하위호환)
64bit
O
64bit
위와같이 생각하시면 됩니다.
32bit CPU에는 64bit 운영체제를 설치할 수 없습니다. 대신 32bit 운영체제를 설치할 수 있고, 32bit 모드로 동작하겠지요.
64bit CPU에는 32bit / 64bit 운영체제를 둘 다 설치할 수 있는데, 다만 32bit 운영체제를 설치하면 32bit 모드로 동작하게 됩니다. 64평짜리 집을 사 놓고, 32평만 사용하는 그런 느낌이지요.
다만 가능은 하다(호환된다) 라고 보시면 됩니다.
이렇게 나중에 나온 더 신식인 녀석(64비트 CPU)가 이전에 나온 구식인 녀석(32비트 CPU)을 사용할 수 있게 해주는 것을 하위 호환성(backward compatibility)라고 합니다.
32비트 시스템과 64비트 시스템의 차이
이제 32비트 시스템과 64비트 시스템의 차이에 대하여 이야기해보도록 하겠습니다.
메모리 주소 공간 크기의 차이(Memory addressing space size)
일단 기본처리 단위가 다르다보니, 프로세서의 레지스터의 크기부터 차이가 납니다. 32비트 프로세서의 범용 레지스터의 크기는 32비트 즉 4바이트이고, 64비트 프로세서의 범용 레지스터의 크기는 64비트, 즉 8바이트입니다.
이렇다 보니, 프로그램 카운터(Program Counter)의 크기로 각각 4바이트 8바이트가 되는데요.
메모리의 주소 모드(address mode)는 기본적으로 바이트당 주소를 하나 할당하는 방식(byte oriented addressing)이므로, 32비트 머신은 최대 32bit의 메모리 어드레싱이 가능하게 됩니다.
//(2^32//)byte의 메모리 주소 공간을 갖는다고 보면 되는데, 이는 4GB에 해당하게 됩니다. 따라서 32비트 머신은 최대 4GB의 메모리밖에 사용할 수 없는 셈이죠.
지금 이 글을 쓰는 시점에도 Windows 10의 커널 메모리 사용량이 꽤 크기 때문에, 쾌적한 컴퓨터 사용 환경을 위해서 가정용 개인 컴퓨터(PC)에도 보통 8GB이상의 메모리를 사용하곤 합니다. 이러한 점을 고려했을때, 32bit 프로세서와 운영체제의 조합은 조금 열악한 환경이 될 수 있겠지요.
그렇다면 64비트 머신은 //(2^64//)인 16엑사바이트의 메모리 주소를 갖겠군요! 라고 생각하실 수 있겠지만, 실제로는 하위 48bit만 사용합니다. 256TB에 해당하는 어드레싱 모드 범위인데요, 왜 그런가 하면 16엑사바이트만큼 큰 양의 메모리 어드레싱이 필요하지 않기 때문이지요.
나중에 필요한 메모리 사이즈와, 실제로 그러한 거대한 크기의 메모리를 만들 수 있다면, 언젠가는 64비트 주소 공간을 다 활용할 수도 있겠지만, 적어도 지금은 아닙니다.
