Daddy's Journey to Platinum

... 
	// string target;
	// vector<string> primitives;
    
	dp[0]=1;
	for(int i=0;i< target.size();i++) 
	{
        if(dp[i])
        { 
            for(int j=0;j<primivites.size();j++) 
            {
                if( primivies[j]==target.substr(i,primitives[j].size()) ) 
                {
                    dp[i+primivies[j].size()] = 1;
                }
            }
        }
    }
    ...

...
	string ones[9] = {"I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    string tens[9] = {"X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    string hundreds[9] = {"C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    string thousands[3] = {"M", "MM", "MMM"};
...
    unordered_map<char, int> m;
    for (int i = 1; i <= N; i++) {
        int num = i;
        
        if (num / 1000 > 0) {
            count(m, thousands[num / 1000 - 1]);
            num %= 1000;
        }
        if (num / 100 > 0) {
            count(m, hundreds[num / 100 - 1]);
            num %= 100;
        }
        if (num / 10 > 0) {
            count(m, tens[num / 10 - 1]);
            num %= 10;
        }
        if (num > 0) {
            count(m, ones[num - 1]);
        }
    }
    if (m.find('I') != m.end()) fout << "I " << m['I'] << endl;
    if (m.find('V') != m.end()) fout << "V " << m['V'] << endl;
    if (m.find('X') != m.end()) fout << "X " << m['X'] << endl;
    if (m.find('L') != m.end()) fout << "L " << m['L'] << endl;
    if (m.find('C') != m.end()) fout << "C " << m['C'] << endl;
    if (m.find('D') != m.end()) fout << "D " << m['D'] << endl;
    if (m.find('M') != m.end()) fout << "M " << m['M'] << endl;
...

void fill_cells(int y, int x, int& direction)
{
    if(visited[y][x]) return;
    visited[y][x] = 1;
    before[y][x] = roomNumber;
    direction++;

    if(!(cells[y][x] & 1)) fill_cells(y,x-1, direction); /// Connected Direction: W
    if(!(cells[y][x] & 2)) fill_cells(y-1,x, direction); /// Connected Direction: N
    if(!(cells[y][x] & 4)) fill_cells(y,x+1, direction); /// Connected Direction: E
    if(!(cells[y][x] & 8)) fill_cells(y+1,x, direction); /// Connected Direction: S
};
...

한 방에 도착하면 연결된 벽을 확인하고, 벽으로 막혀 있지 않으면 그 방까지 연결한다.

 /// visit every rooms
    for(int y=1; y <N+1; ++y)
    {
        for(int x=1; x<M+1;++x)
        {
            if(!visited[y][x])
            {
                roomNumber++;
                int tn=0;
                fill_cells(y,x,tn);
                room[roomNumber] = tn;
                if( tn > maxn ) maxn = tn;
            }
        }
    }

    /// remove wall check
    for(int j=1;j<=M;j+=1)
    {
        for(int i=N;i>=1;i-=1)
        {
            if(cells[i][j]&2)if(before[i-1][j] && before[i-1][j]!=before[i][j])
            {
                if( room[before[i-1][j]] + room[before[i][j]] > max2n )
                {
                    max2n = room[before[i-1][j]] + room[before[i][j]];
                    wx = i,wy = j,wd = 'N';
                }
            }

            if(cells[i][j]&4)if(before[i][j+1] && before[i][j+1]!=before[i][j])
            {
                if( room[before[i][j+1]] + room[before[i][j]] > max2n )
                {
                    max2n = room[before[i][j+1]] + room[before[i][j]];
                    wx = i,wy = j,wd = 'E';
                }
            }
        }
    }

전체 방에 대해서 벽을 제거해서 결과값이 최대가 될때마다 제거하는 벽을 기록하는 방법을 적용한다.

int getHammingDistance(int a, int b)
{
    int ret=0;

    while( a> 0 || b>0)
    {
        if( a%2 != b%2)
            ret++;
        a /= 2;
        b /= 2;
    }
    return ret;
};

...

  ans.push_back(0);
    /// check hamming distance > D, put result
    for(int i=0;i < maxB ;i++)
    {
        bool ok= true;

        /// compare hamming distance with last code
        for(int j=0;j!=ans.size();j++)
        {
            /// distance < D
            if( getHammingDistance(i,ans[j]) < D )
            {
                ok = false;
                break;
            }
        }
        /// distance >= D
        if(ok)
        {
            ans.push_back(i);
        }

        /// Max output number
        if(ans.size() >= N)
        {
                break;
        }
    }