사과담기

이문제 비트 연산으로 풀려고 시간 다 때려박아 넣었는데 거의 다된거 같은쯤에..

BFS가 필요한가..?? 라고 생각하다가 도저히 안되서 해설 강의 듣는데

그냥 대소 비교만 했음. 아주 간단하게 풀었는데

강의를 듣고 바로 계산기 켜서 비트값 이리저리 켜보다가

	if (dir)
	{
        if (Cango(s >> 1))
        {
          s >>= 1; ++cnt;
        }
		else dir = (++dir) % 2;
	}
	else
	{
		if (Cango(s << 1))
		{
			s <<= 1; ++cnt;
		}
		else dir = (++dir) % 2;		
    }

이런식으로 방향에 따라서 좌/우 로 갈지 막 고민을 엄청했는데 이게 아니라

아래코드처럼 그냥 pp값보다 큰지 작은지를 보고 이동시켰으면 되었던 문제이다...

#include <iostream>
#include <math.h>
using namespace std;
#define endl "\n"

int n, m, j, p, s = 0, dir = 1, bound = 2049, cnt = 0, pos[11];

bool Cango(int s)
{
	if (s & bound) return false;
	else if (s & bound) return false;
	return true;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	cin >> j;

	for (int i = 1; i < 11; ++i) pos[i] = pow(2, i);

	for (int i = 10; i > 10 - m; --i) s |= pos[i];

	for (int i = 0; i < j; ++i)
	{
		cin >> p;
		int pp = pos[11 - p];

		while (!(s & pp))
		{
			if (pp < s)
			{
				if (Cango(s >> 1))
				{
					s >>= 1; ++cnt;
				}
				else dir = (++dir) % 2;
			}
			else if (pp > s)
			{
				if (Cango(s << 1))
				{
					s <<= 1; ++cnt;
				}
				else dir = (++dir) % 2;
			}
		}
	}

	cout << cnt;

	return 0;
}

해설

스크린을 이런식으로도 볼 수 있겠다..

그리고 이 문제는 BFS, DFS이딴거 사용 안해도 되는 문제이다.

문제를 읽고 이해를 하고 최대 최소 확인하고

무식하게 풀 수 있는지 생각한뒤에 BFS, DFS를 생각해야한다.

cpp 코드

#include <iostream>
#include <math.h>
#include <queue>
#include <vector>
using namespace std;
#define endl "\n"

int n, m, j, l, r, temp, ret;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	cin >> j;

	l = 1;

	for (int i = 0; i < j; ++i)
	{
		r = l + m - 1;

		cin >> temp;
		if (temp >= l && temp <= r) continue;
		else
		{
			if (temp < l)
			{
				ret += (l - temp);
				l = temp;
			}
			else
			{
				l += (temp - r);
				ret += (temp - r);
			}
		}
	}

	cout << ret;
	
	return 0;
}