문제 정보문제상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.사탕의 색이 다른 인접한 두 칸이..

주사위 굴리기 문제 풀이 문제 파악 필요한 기능 이동 이동시에는 지도 밖으로 나가는지 확인해야 하는 조건 필요 이동 시 주사위 배열의 위치를 변경시켜줘야 함 바닥면 복사 바닥이 0 일 경우 주사위의 바닥면을 바닥에 복사 바닥이 0 이 아닐경우 바닥의 수를 주사위 바닥면에 복사 후 바닥의 값은 0으로 변경 변수 생성 지도 생성에 필요한 변수 현재 위치 변수 주사위 오더 횟수 변수 동서남북 이동시 필요한 x,y 이동 배열 변수 주사위 배열 변수 public static int n,m,x,y,k; public static int[][] map; //동,서,북,남 public static int[] dx = {0,0,-1,1}; public static int[] dy = {1, -1, 0, 0}; //윗,바,..

크게 어렵지 않은 문제이므로 간단한 문제풀이 절차만 적어보겠다. 1. 수는 1000000000 보다 작거나 같은 자연수라고 했다. 자릿수를 보면 10자리이다. 2. 시간복잡도로 선택정렬을 사용한다면 각 자리 숫자를 완전탐색한다면 O(N^2)의 복잡도를 가지므로 10 * 10 = 100회의 연산을 거친다. 3. 1초당 1억번의 연산을 기준으로 잡는다면 충분히 선택 정렬을 사용해도 무방하다!\ 4. BuffredReader와 StringTokenizer로 입력을 받아 연산해준다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; pu..

필요 알고리즘 개념 그리디 일정한 규칙을 정해 매번 해당 규칙을 적용하다보면 답이 나오는 알고리즘 우선순위 큐 우선순위 큐는 자동으로 수가 우선순위대로 정렬된다. 우선 순위 큐를 사용해 mini heap을 사용 풀이 위 문제의 핵심은 연산 과정의 중간 결과가 다시 연산에 사용된다는 것 매번 가장 작은 2개를 뽑아 더해주면 된다 백준문제의 예시 1. 3개의 수를 받는다. 10 / 20 / 40 2. 연산 시작 10+20 =30 30을 합계에 포함한다. 중간 연산의 30을 다시 큐에 넣어준다. 30/40 3. 두 번째 연산 30+40 70을 합계에 포함한다. 결과 = 100 코드구현 import java.util.PriorityQueue; import java.util.Scanner; public class..

문제를 풀기 전에 우선 구간합을 구하는 방법을 알아야한다. 하지만 또! 구간합을 구하기 전에 합 배열을 만들줄 알아야 한다. ㅎㅎ 알아야하는 이유는 다음과 같다. 반복문으로 해당 문제를 풀었을때에는 시간 초과가 발생했다. 주어진 질의의 개수가 최대 10만개이다. 수의 개수도 최대 10만개이다. 최악의 경우에는 10만개의 수를 가진 배열안에서 10만번의 질의를 반복문을 돌려야한다. 이때 반복문을 통한 시간복잡도 O(n^2)로는 해결할 수 없다. 이 때 구간합으로 문제를 해결한다면 누적배열합을 생성하는데 O(N)이 들고 M번 반복하므로 O(N+M)의 시간복잡도를 갖는다. 해당 문제는 1초안에 풀어야하는데 구간합 알고리즘을 모른다면 반복문으로 통해 최악의경우 1억회이상의 연산을 하기때문에 시간내에 풀기 힘들것..