본문 바로가기

분류 전체보기

 (215)
백준 10972 다음 순열 (Java) 1. 문제 링크 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 그냥 순열로 문제를 풀게 될 경우 N이 너무 커서 시간초과가 발생한다. 그래서 규칙을 찾는데 한참 걸렸다.. 온갖 방법을 총동원해서 찾은 규칙이다. 항상 순열의 뒤에서부터 바뀌는 범위가 넓어진다. ex) 1 2 3 4 -> 1 2 3 4 -> 1 3 2 4 -> 1 3 4 2 -> 1 4 2 3 -> 1 4 3 2 -> 2 1 3 4 뒤에서부터 오름차순을 확인하면서 처음으로 오름차순이 아닌 값(now)을 찾는다. 만약 뒤에서부터 처음까지 전부 오름차순일 경우, 다음 ..
백준 9655 돌 게임 (Java) 1. 문제 링크 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 문제에서 시작이 상근이라는 것과 1개 또는 3개의 돌만 가져갈 수 있다는 점에 주목했다. 돌이 1개인 경우, 상근이가 이긴다. (1) 돌이 2개인 경우, 창영이가 이긴다. (1 -> 1) 돌이 3개인 경우, 상근이가 이긴다. (3) 돌이 4개인 경우, 창영이가 이긴다. (1 -> 3) (3 -> 1) 돌이 5개인 경우, 상근이가 이긴다. (1 -> 1 -> 3) (1 -> 3 -> 1) 이런 식으로 주어진 돌이 홀수라면 상근이가, 짝수라면 창영이가 이기는 규칙을 알 수 있다. 4. 코드 import java.io.Buffere..
백준 11727 2xn 타일링 2 (Java) 1. 문제 링크 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 앞서 올린 2xn 타일링을 응용한 예제이다. 2xN 타일링 문제와 시작은 똑같다. 대신 2x2 타일이 새로 생겨서 그 경우의 수를 알아야 한다. 그려 보니까 2개 이상 차이가 나는 경우에 2x2 타일을 추가할 수 있었다. 즉, a[i] = a[i-1] + a[i-2]*2라는 점화식이 나온다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; public clas..
백준 11726 2xN 타일링 (Java) 1. 문제 링크 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 하나씩 그려보면 a[i] = a[i-1] + a[i-2] 라는 점화식이 나온다는 것을 알 수 있다. 그려보면 간단하게 알 수 있다. 문제를 읽어보면 10007로 나눈 나머지를 출력하라고 하는데 마지막 결과에서만 나눠서 답이 나오지는 않는다. 앞선 배열의 값을 이용하기 때문에 모든 값을 저장하기 전에 나누는 과정이 필요하다. 그리고 1이 들어간 경우나 2가 들어간 경우도 생각해야 된다. 4. 코드 import java.io.Buf..
백준 2164 카드2 (Java) 1. 문제 링크 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 큐를 이용해서 전부 큐에 넣은 후 하나는 꺼내서 버리고 하나는 다시 넣는 방식으로 진행했다. 하나만 남았을 경우 종료해야 하는데 if문 위치를 적절하게 두 번 넣어서 예외가 발생하지 않도록 했다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Q..
백준 7576 토마토 (Java) 1. 문제 링크 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 큐를 이용해서 풀었다. 익은 토마토를 큐에 넣어두고 하나씩 꺼내면서 사방탐색을 하는 방식이다. 큐가 비어있으면 종료하고 전체 토마토 중 안 익은 토마토가 있으면 -1을 출력한다. 날짜를 저장하기 위해서 day라는 배열을 만들어서 사용했다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.Input..
백준 14501 퇴사 (Java) 1. 문제 링크 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 dp 느낌으로 뒤에서부터 시작했다. 끝나는 날이 퇴사 이후라면 이전과 같은 금액이다. 그 외의 경우에는 상담 이전 금액과 지금 금액 + 이후 금액의 합 중 큰 값이 오면 된다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReade..
백준 1244 스위치 켜고 끄기 (Java) 1. 문제 링크 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 문제에 나와있는 내용을 차근차근 풀면 된다. 주의할 점은 스위치가 1번부터 시작된다는 것이다. 또한 20개씩 나눠서 출력해야 한다는 점도 꼭 보고 제출합시다.. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private static int[] btn; public static void..

티스토리툴바