다시푸는 코딩 테스트 준비 일지
문제
김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다.
마침 이 스타 대회에 임한수도 참가했다. 김지민은 갑자기 스타 대회에서 우승하는 욕심은 없어지고, 몇 라운드에서 임한수와 대결하는지 궁금해졌다. 일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다. 1 라운드에서 김지민의 번호와 임한수의 번호가 주어질 때, 과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 참가자의 수 N과 1 라운드에서 김지민의 번호와 임한수의 번호가 순서대로 주어진다. N은 2보다 크거나 같고, 100,000보다 작거나 같은 자연수이고, 김지민의 번호와 임한수의 번호는 N보다 작거나 같은 자연수이고, 서로 다르다.
출력
첫째 줄에 김지민과 임한수가 대결하는 라운드 번호를 출력한다. 만약 서로 대결하지 않을 때는 -1을 출력한다.
예제 입력 1 복사
16 1 2
예제 출력 1 복사
1
예제 입력 2 복사
16 8 9
예제 출력 2 복사
4
예제 입력 3 복사
1000 20 31
예제 출력 3 복사
4
예제 입력 4 복사
65536 1000 35000
예제 출력 4 복사
16
예제 입력 5 복사
60000 101 891
예제 출력 5 복사
10문제 풀이 접근
이 문제를 풀면서 접근한 나의 아이디어는2명씩 대결하는 스타 경기에서 우측을 기준으로 2로 나누는 것이었다.
예를들어, 1번 - 2번이 붙을때 2번을 기준으로 /2 를 수행하면 그 다음 라운드인 2R에서 1번으로 번호표를 받을테니 (해당 번호표)/2 를 했다.
물론 2번과 같이 짝수일 경우는 바로 나눴지만 홀수 일 경우는 +1을 해주어서 나눠야한다.
이유는 1/2 = 0.5로 번호표는 1번부터 시작해야하는 경우가 안맞기 때문에, 시작은 1번부터 할 수 있도록 제약을 두었다.
사실 0번으로 시작해도 무방은 할 수 있겠으나, 나는 1번 번호표가 무조건 첫번째 번호표다 라는 것을 가정했다.
그리고, 염두해두어야할 것은, 앞의 사람 (문제에서, 김지민)의 번호표가 뒷 사람(문제에서 임한수)의 번호표가 무조건 작지 않다는 것을 염두해두어야 한다.
일단 문제는 서로 다른 번호표를 갖고는 있느나, 무조건 김지민의 번호가 임한수의 번호보다 작다라는 제약이 없다.
대표적인 반례는 9 9 7 이다. 김지민의 번호가 9 , 임한수의 번호가 7 일 경우 올바르게 연산해주지 않는다면 문제를 해결할 수 없다.
먼저 루프하면서 새롭게 번호표를 뽑는 로직은 짝수일 경우 (x)/2 , 홀수일 경우 (x+1)/2로 해두었고, 루프를 정지할 조건식을 짜야하는데, 이 조건식은 var1 의 수가 홀수이며, var1 + 1 = var2 가 되어야 한다고 해야한다.
그렇지 않으면 16 8 9 같은 경우에 1-2, 3-4, 5-6, 7-8, 9-10 이렇게 조가 짜여지는데, 인접하다고 판단해서 1을 찍고 리턴을 할 수 있다.
그래서 var1이 홀수일때를 기준으로 잡고 +1 해서 var2 와 같다면 1의경우 2와 조가 짜여지는 것 처럼 조건식을 설정할 수 있다.
이는, 김지민의 번호가 클때도 산정해야하므로, var2 의 수가 홀수이며, var2 + 1 = var1도 조건식으로 넣어야한다.
마지막으로, 문제풀면서 내가 놓친 부분은 둘의 대진은 무조건 1번 ,2번으로만 만난다는 착각을해서 시간이 오래걸렸다.
이 케이스의 반례는 1000 20 31 이다.
김지민은 20(1R) - 10(2R) - 5(3R) - 3(4R) - 1 의 번호표를 뽑고,
임한수는 31(1R) - 16(2R) - 8(3R) - 4(4R) - ? 로 3-4의 조(4R) 에서 만난다.
이는 위에 말해놓은 조건식에도 충족되는 값이다.
정답 작성 코드 (C#)
using System;
using System.CodeDom;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Security.AccessControl;
using System.Security.Authentication;
using System.Security.Cryptography;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Web;
using System.Xml.Linq;
using static CodingTestProj.Program;
/*
* Difficulty : Middle
* URL : https://www.acmicpc.net/problem/1057
* Time : 59m 17s
*/
namespace CodingTestProj
{
internal class Program
{
static void Main(string[] args)
{
Solution solution = new Solution();
solution.solve();
}
}
public class Solution
{
int people;
decimal n;
decimal m;
decimal nRound;
public void solve()
{
nRound = 1;
string[] input = Console.ReadLine().Split(' ');
people = Int32.Parse(input[0]);
n = decimal.Parse(input[1]);
m = decimal.Parse(input[2]);
if(m % 2 == 0 && m -1 == n)
{
Console.WriteLine(1);
return;
}
finder(n,m, nRound);
Console.WriteLine(nRound);
}
public void finder(decimal var1 ,decimal var2, decimal round)
{
if (nRound > ((people / 2) + 10))
return;
if (var1 % 2 == 1 && var2 == var1 +1)
{
nRound = round;
return;
}
if (var2 % 2 == 1 && var1 == var2 + 1)
{
nRound = round;
return;
}
var var1next = (var1 % 2 == 1) && (var1 != 1) ? var1 + 1 : var1;
var var2next = (var2 % 2 == 1) && (var2 != 1) ? var2 + 1 : var2;
var var1Div = (var1 == 1) ? 1 : var1next / 2;
var var2Div = (var2 == 1) ? 1 : var2next / 2;
finder(var1Div, var2Div, ++round);
}
}
}
코드 결과
