글 읽기 - 하노이탑 k번째 이동 기둥 문제...

kwak2418 2년 전 0

비트마스크를 통한 계산으로 90점 까지 통과했습니다... 어떤 것이 문제일까요 , 이 사이트에는 없는 문제를 질문하여 죄송합니다.. 도저히 못 찾겠습니다.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define endl "\n"
typedef unsigned long long int ulli;


/*
원판 넘버(k) -> 2진수를 원판 넘버

몇번 반복했는지(원판 넘버) -> int 이동 횟수
출력함수(원판갯수,원판번호,이동횟수)  -> start -> dest 

*/
int disk_num(ulli q) //해당 k시 이동하는 원판 번호
{
	int count=0; 
	while(q%2==0) // 처음으로 1 나오는 이진수 자릿수 찾기 
		{
			count++;
			q=q>>1;
		}
	// count=2  100 ,  3번 원판 
	return count+1;
}

ulli move_count(ulli q,int diskNum)
{
    //100 -> 3
    //110100 -> 52,   110(6) +1 =7번 째
	cout << diskNum <<endl;
	return ((q>>diskNum)+1);
}

void solution(const int n,const int diskNum,const ulli move)
{
	int divid_n=n%2;
	int divid_disk=diskNum%2;
	if(divid_n==divid_disk) //짝수 짝수, 홀수 홀수
	{
		// A->C->B->A
		switch(move%3)
			{
				case 0:     //3번째 이동 (2->1) (B->A)
							cout <<"2 1"<<endl;
							break;
				case 1:    // 1번째 이동 (A->C)
							cout <<"1 3"<<endl;
							break;
				case 2:     // 2번째 C->B
							cout <<"3 2"<<endl;
							break;
			}
	}
	else
	{
		//A->B->C->A
		switch(move%3)
			{
				case 0:    //3번째 이동 (2->1) (C->A)
							cout <<"3 1"<<endl;
							break;
				case 1:    //1번째 이동
							cout <<"1 2"<<endl;
							break;
				case 2:     //2번째 이동
							cout <<"2 3"<<endl;
							break;
			}
		
	}
	
}



int main()
{
    int tc = 0;
    cin >> tc;
    while (tc--)
    {
		  int n;
		  ulli k;
		  cin >> n >> k;
		  int diskNum=disk_num(k);
		  ulli moveCount=move_count(k,diskNum);
		  solution(n,diskNum,moveCount);
		    
		
    }
    return 0;
}

kwak2418 2년 전 0

네 방금 제출했는데 바로 통과했습니다...

n=64 k=18446744073709551615

2 3역시 출력이 됩니다..

startlink 2년 전 1

일단 n ≤ 60 이고, n ≤ 20인 모든 경우에 대해서 입력을 다 넣어보았는데, 틀리지 않을걸 보니 다른 요인이 있는 것 같습니다.

kwak2418 2년 전 0

데이터 타입이나 비트연산도 문제가 발생할 부분이 있을까요 .. 2^64라 unsigned long long int를 사용 했는데요..

입력은 표준입력(standard input)을 사용한다. 입력은 t 개의 테스트 케이스로 주어진다. 입력 파일 의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 t 개의 줄에 는 한 줄에 한 개의 테스트 케이스에 해당하는 정수들이 주어진다. 각 테스트 케이스에 해당되는 각 줄에두개의정수n,k가주어지는데,첫번째정수n(1≤ n ≤ 64)은HanoiTower문제에서주 어지는 원반의 개수이며, 그 다음 정수 k (1 ≤ k < 2n-1) 는 k 번째 옮길 원반을 나타낸다.

출력은 표준출력(standard output)을 사용한다. 입력되는 테스트 케이스의 순서대로 다음 줄에 이어 서 각 테스트 케이스의 결과를 출력한다. 각 테스트 케이스에 해당하는 출력의 첫 줄에 k 번째로 옮 겨질 원반의 source 기둥 번호와 target 기둥 번호를 출력한다. 두 정수 사이에는 한 개의 공백을 둔 다.

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

문제

문제

출처

ICPC

하노이탑 k번째 이동 기둥 문제...

kwak2418 2년 전 0

startlink 2년 전 1

kwak2418 2년 전 0

kwak2418 2년 전 0

startlink 2년 전 1

kwak2418 2년 전 0

kwak2418 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말