본문 바로가기

코딩 테스트

[Java] 12026 BOJ 거리 문제 문제 BOJ 거리는 보도블록 N개가 일렬로 놓여진 형태의 도로이다. 도로의 보도블록은 1번부터 N번까지 번호가 매겨져 있다. 스타트의 집은 1번에 있고, 링크의 집은 N번에 있다. 스타트는 링크를 만나기 위해서 점프해가려고 한다. BOJ거리의 각 보도블록에는 B, O, J 중에 하나가 쓰여 있다. 1번은 반드시 B이다. 스타트는 점프를 통해서 다른 보도블록으로 이동할 수 있다. 이때, 항상 번호가 증가하는 방향으로 점프를 해야 한다. 만약, 스타트가 현재 있는 곳이 i번이라면, i+1번부터 N번까지로 점프를 할 수 있다. 한 번 k칸 만큼 점프를 하는데 필요한 에너지의 양은 k*k이다. 스타트는 BOJ를 외치면서 링크를 만나러 가려고 한다. 따라서, 스타트는 B, O, J, B, O, J, B, O.. 더보기
[Java] 11729 2xN 타일 문제 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 문제 풀이 전형적인 DP 문제이다. 초반에 조금 생각해보면 도형이 1개 놓여졌을 때부터 경우의 수를 생각해보면 세로로 타일을 놓는 경우 1개 밖에 없다. 다음으로 2개를 놓았을 때의 방법은 가로로 두개를 놓는 방법과 기존의 세로로 타일을 놓았던 경우에서 옆에 세로로 하나 더 두는 방법 총 2개가 나온다. 계속 진행해보자 3개의 타일을 놓을 수 있는 경우의 수는 2개를 놓는.. 더보기
[Java] 1463 1로 만들기 문제 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 예제 입력 1 2 예제 출력 1 1 예제 입력 2 10 예제 출력 2 3 힌트 10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다. 문제 풀이 경우의 수를 모두 확인하면서 그 최소 값을 찾았다. 입력받은 N부터 3으로 나누어 떨어지면 /3 한 값을 .. 더보기
[Java] 6603 로또 문제 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은, 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우, 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34]) 집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있.. 더보기
[Java] 14225 부분수열의 합 문제 문제 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다. 입력 첫째 줄에 수열 S의 크기 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 수열 S가 주어진다. S를 이루고있는 수는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다. 문제 풀이 숫자의 범위는 10만이고 갯수는 최대 20개이다. 즉 발생할 수 있는 합은 20 * 100000 이다. 해당 크.. 더보기
[Java] 2528 부등호 문제 문제 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. A ⇒ 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 3 1 7 0 이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데, 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예.. 더보기
[Java] 15661 링크와 스타트 문제 문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이다. 이제 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다. N=4이고, S가 아래와 같은 경우를 살.. 더보기
[Java] 14501 퇴사 문제 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일 2일 3일 4일 5일 6일 7일 Ti 3 5 1 1 2 4 2 Pi 10 20 10 20 15 40 200 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은.. 더보기

티스토리툴바