SWEA 22574. 높은 곳으로

1부터 n번 까지의 차례 동안 현재 위치에서 차례 만큼 올라갈 수 있을 때, 특정 위치 P에 닿지 않고 도달할 수 있는 최고 높이를 구하는 문제이다.

 

처음에는 직접 여러 경우의 수를 세려고 했으나 이는 경우의 수가 많아 불가능하였고, 매 차례마다 올라가다가 P에 도달하게 되면 이전 높이 중 가장 낮게 올라간 1번 차례에만 올라가지 않고 올라가면 최고 높이에 올라갈 수 있게 된다.

int n = Integer.parseInt(st.nextToken()), p = Integer.parseInt(st.nextToken());
if ((n * (n + 1)) / 2 < p) {
    sb.append((n * (n + 1)) / 2).append('\n');
    continue;
}
int sum = (n * (n + 1)) / 2;
int current = 0;
for (int i = 1; i <= n; i++) {
    current += i;
    if (current == p) {
        sum--;
        break;
    }
    if(current > p) {
        break;
    }
}

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while (tc-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken()), p = Integer.parseInt(st.nextToken());
            if ((n * (n + 1)) / 2 < p) {
                sb.append((n * (n + 1)) / 2).append('\n');
                continue;
            }
            int sum = (n * (n + 1)) / 2;
            int current = 0;
            for (int i = 1; i <= n; i++) {
                current += i;
                if (current == p) {
                    sum--;
                    break;
                }
                if (current > p) {
                    break;
                }
            }
            sb.append(sum).append('\n');
        }

        br.close();
        System.out.print(sb);
    }
}