YataNox

문제문제뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다.주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까?게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다.플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다. 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다. 도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 ..

문제문제여러분은 요즘 유행하는 심리검사인 MBTI에 대해 들어보았는가?MBTI(Myers-Briggs Type Indicator)는 C.G.Jung의 심리유형론을 근거로 하여Katharine Cook Briggs와 Isabel Briggs Myers가 보다 쉽고 일상생활에 유용하게 활용할 수 있도록 고안한 자기보고식 성격유형지표이다. (출처: 위키백과)MBTI는 아래와 같이 네 가지 척도로 사람들의 성격을 구분한다.외향(E) / 내향(I)감각(S) / 직관(N)사고(T) / 감정(F)판단(J) / 인식(P)각 척도마다 두 가지 분류가 존재하므로, MBTI는 총 $2^4 = 16$가지 유형이 있음을 알 수 있다. 일반적으로 MBTI의 유형들은 각 분류를 나타내는 알파벳 한 글자씩을 따 네 글자로 표시하게 ..

문제문제절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.배열에 정수 x (x ≠ 0)를 넣는다.배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다.입력첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.출력입력에서 0이 주어진 회수만큼 답을 ..

문제N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.P1 IOIP2 IOIOIP3 IOIOIOIPN IOIOI...OI (O가 N개)I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.출력S에 PN이 몇 군데 포함되어 있는지 출력한다.문제 풀이부분 점수가 있는 문제이다. 번호배점제한 150N ≤ 100, M ≤ 10 000.250추가적인 제약 조건이 없다.처음에는 단순히 I가 나오는 위치부터 한 칸 씩 옆을 비교하면서 처리를 했다. 당연하게도 50점을 받았다.더보기import java.io..

문제 문제널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.배열에 자연수 x를 넣는다.배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다.입력첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고,x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.출력입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 ..

문제 문제2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×17 직사각형을 채운 한가지 예이다.입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.문제 풀이이전에 풀었던 문제의 연장선이다. 이전 문제에서 n - 2의 타일에 붙이는 타일은 2x1타일이 가로로 2개 붙은 형태만 가능했었는데, 타일이 추가되면서 대신 2x2타일도 가능하게 된 것을 알 수 있다. 점화식으로 표현하면 dp[n] = dp[n-1] + (2 * dp[n-2])가 된다.  각 DP를 계산할 때 10007을 나머지연산 해주는 것도 잊지 말아야한다. [Java] 11729 2..

문제M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다.ㅇ 위의 그림은 M=5, N=3의 예이다.이제 표의 왼쪽 위 칸(○)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 그려진 칸에 닿아서 더 이상 이동할 수 없게 되면, 시계방향으로 선을 꺾어서 그려나간다.ㅇ → ↘↗ ↘ ↓↑ ↓ ↓↑ 끝 ↓↖ ← ↙위의 표는 선을 그려 나간 모양을 나타낸 것이다. 선이 꺾어진 부분은 대각선으로 나타내었다. 표의 모든 칸이 채워질 때까지 선을 몇 번 꺾게 될까? 또, 어디에서 끝나게 될까?입력첫째 줄에 M과 N이 빈 칸을 사이에 두고 주어진다. (2 ≤ M, N ≤ 2,100,000,000)출력첫째 줄에 표의 모든 칸이 채워질 때까지 선..

문제문제어른 상어가 마법사가 되었고, 파이어볼을 배웠다.마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다. 가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있다.i번 파이어볼의 위치는 (ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다.위치 (r, c)는 r행 c열을 의미한다.격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고,1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다.7 0 16 25 4 3마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다.모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.이동하는 중에..