www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 자신의 번호가 들어갈 수 있는 배열을 하나 만든다(0 초기화) 그리디 탐색으로 보고있는 자리가 비워져있다면 나보다 큰 사람이 들어갈 곳으로 판단해서 cnt를 1감소시킨다. cnt가 0이라 나보다 큰 애는 없어도 자리가 비워져있지 않다면 나보다 작은 친구가 들어간 곳이다. 다음 공간을 본다. cnt도 0이고 현재 공간이 0이면 내가 들어갈 자리이다. import java.util.Scanner; publi..
www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 문제자체는 어렵지 않은데 시간초과가 있어서 최적화해줘야한다. --- 풀이 r길이는 2인데 속도가 1000이라면 엄청나게 왔다갔다해야된다. 같은 위치에 있을 경우의 규칙을 찾아야된다. 주의할 점은 같은 위치에 있더라도 방향이 반대인 것은 같은 경우가 아니다! 예를 들면 C=5이고 현재 열 번호 1에 있고 우로 움직이는 상어가 있다고 하자 열 번호 1 2 3 4 5 인 경우 S=1이면 오른쪽으로..
www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net subset을 사용해서 처리해줬다. 길이가 1이상이라는 조건이 있다 import java.util.Scanner; public class Main { static int n,s; static int[] arr; static int answer; public static void main(String[] args) { Scanner sc=new Scanner(System.in)..
프로그래머스에서 java를 쓰니 매우 어색하다 네이버 코테 대비로 연습 중 ㅠ javascript 쓸 것 같지만 문자열 처리 나오면 javascript로 해야지 -- 풀이 우선순위 큐에 모든 음식을 넣는다. 음식을 모두 섞는데 만약 가장 작은 수가 K 이상이면 조건을 만족하므로 break 아니면 섞는다. 만약 음식이 1개가 남으면 섞지 못하므로 break해주고 마지막 1개 음식이 K를 넘는지 확인한다. 아니면 최종까지 불가능한 것이므로 -1을 리턴해준다. import java.util.*; class Solution { public int solution(int[] s, int K) { int answer = 0; PriorityQueue pq=new PriorityQueue(); for(int i=0;..
www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 청소년 상어를 풀고나서 이 문제를 푸니 dfs가 익숙해서 dfs로 경우를 탐색하다가 메모리 초과가 났다. 가끔 bfs로만 되거나 dfs만 되는 문제들이 있어서 헷갈리는데 최단 시간 (같은 위치 구간에서 동시에 탐색할 때)는 bfs이고 모든 경우의 수를 다 돌아봐야하는 경우 (청소년 상어처럼 먹는 물고기 번호가 가장 큰것을 구하는 것)은 dfs인 것 같다. 물이 차오를 지역도 못간다는 것은 즉, 물이 찬 것과 같다라는 뜻이라..
www.acmicpc.net/problem/17276 17276번: 배열 돌리기 각 테스트 케이스에 대해 회전 연산을 마친 후 배열의 상태를 출력한다. n줄에 걸쳐 각 줄에 n개의 정수를 공백으로 구분하여 출력한다. www.acmicpc.net 대각선 45도, -45도로 배열을 돌리는 문제. 주 대각선들 외에는 그대로 냅둔다. import java.util.Scanner; public class Main { static int n,t,d; public static void main(String[] args) { Scanner sc=new Scanner(System.in); t=sc.nextInt(); for (int tc = 1; tc
www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 다른 것은 일반 bfs문제와 크게 다를 것이 없는데 배열 회전하는 부분이 어려웠다 ㅠㅠ 예전에 한 번 해봐서 괜찮겠지 했는데 수학 계산을 못하겠어서ㅋㅋㅋㅋㅋ 길이가 4일때 첫 열의 세로줄 2 1 5 7 을 첫 행의 가로줄로 만들기 위해서 2 1 5 7 가로줄의 열 번호와 행번호를 sx, sy라는 변수를 따로 만들어서 증가시키고 첫 열의 세로줄은 for문의 변수를 돌리는 방식으로 해줬다. 내일..
www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net arraylist는 검사 시작점과 연합국인 곳들의 좌표가 들어가는 리스트이다. 1. 방문 안된 곳에서 상하좌우를 검사하면서 경계를 열 수있는 곳을 검사한다. 연합국이 되면 sum+=연합국 인구수, cnt(연합국에 들어가는 개수)+1해주고 arraylist에 새로운 연합국의 좌표를 넣어준다. 2. 시작한 곳에서 bfs로 최대한 검사할 수 있는 곳까지 다 검사가 끝나면 arraylist 좌표에 해당하..
푸는 데 소요시간: 40분 파이프 방향이 위일때는 다음 칸의 파이프가 방향 아래를 포함하고 있으면 된다. 이처럼 다음 칸의 방향이 내 방향의 반대인 숫자를 가지고 있나 체크해주면 된다. import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y,x,type; public Pos(int y, int x,int type) { super(); this.y = y; this.x = x; this.type=type; } } public class Solution { static int t,m,n,l; static int[][] map; static int[]..
www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net import java.util.ArrayList; import java.util.Scanner; public class Main { static int n,k; static int[] belt; static ArrayList list=new ArrayList(); static boolean[] pos; public static void main(String[] args) { Scanner ..