BOJ
-
BOJ) 리모컨알고리즘/백준 2020. 7. 11. 20:22
리모컨 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼�� www.acmicpc.net 풀이 리모콘이 고장나면 고치거나 바꿔야하는데, 그대로 써서 골치아프게한 문제다. 우선, 1~9 버튼과 채널 위아래 이동 + - 버튼 11개가 있는 리모컨이다. 그리고, 입력에서 버튼이 고장난 갯수와 버튼의 위치를 알려주는데, 여기서 런타임에러가 한번 떴다. 처음에는 if(n !=ZERO)를 해주지 않아서, n이 0인 경우 ( 고장난 버튼이 없는 경우 ) 에 입력을 받고 저장하려고 시도해서 에러가 났다. 그래서 if문을 통해 걸러줬다. ..
-
BOJ) 카드 구매하기알고리즘/백준 2020. 7. 8. 20:07
카드 구매하기 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 갑자기 dp문제를 풀고싶어서 이 문제를 풀었다. 이 문제는 한번에 정답을 맞추지 못했다. 총 세번을 제출했는데, 첫번째는, 에라토스테네스의 체를 이용해서 소수를 판별하는 것처럼, 특정 인덱스 i 에서 n까지 i 씩 증가하면서 초기에 저장된 가격과 i를 여러번 곱한 값 중 더 큰 값을 저장해주었다. for(int i=1; i
-
BOJ) 유기농 배추알고리즘/백준 2020. 7. 8. 19:53
유기농 배추 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 풀이 이 문제도 grouping 문제여서, find-union을 써볼까 했지만, 크게 효율적일 것 같다는 느낌이 없었고, 이 문제에 적용하기에는 조금 복잡해질 것 같다고 생각했다. 그래서 그냥 BFS로 풀었다.. ㅎㅎㅎ 총 세번을 제출했고, BFS, BFS, DFS 순으로 제출했다. 첫번째는 평소에 풀던 것 처럼 grouping을 해주면서, gourping이 끝난 이후 저장된 groupIdx를 출력해줬다. 하지만, group을 지어서 값을 변경하거나 이용하지..
-
BOJ) 파이프 옮기기 1알고리즘/백준 2020. 7. 8. 19:37
파이프 옮기기 1 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 옮길 수 있는 모든 경우의 수를 찾는 문제기 때문에 브루트포스 문제다. 직접 다 돌리는데는 BFS나 DFS만큼 편한게 없다고(?) 생각해서 DFS로 풀었다. 문제를 풀면서 막혔던 부분은 첫째로, 문제 조건을 잘못 이해했다는 것이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수 이 문구에서 N,N을 보지 않고 N,y or x,N으로 이동한 파이프들을 구해줬었다... 두번째로는 실수라기 보다는 기둥의 시작점..
-
BOJ) 인구 이동알고리즘/백준 2020. 7. 7. 20:28
인구 이동 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모�� www.acmicpc.net 풀이 인접해있는 땅과 인구의 차이가 주어진 L과 R 사이에 존재하면 평균을 내면서, L과 R 사이에 존재하지 않을 때 까지 묶어주는 문제다. 처음 제출하자마자 맞았지만, 효율성이 조금 떨어진다고 생각해서 코드를 수정했다. 얼마 전 포스팅했던 성곽 문제랑 푸는 방법이 비슷하다. grouping을 해주고 각 group의 평균 값을 HashMap에 저장한다. 전체 grouping이 끝나면, 각 gourp마다 평균 값을 넣어주면서 조건에 부합..
-
BOJ) 에디터알고리즘/백준 2020. 7. 7. 20:09
에디터 1406번: 에디터 문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 www.acmicpc.net 풀이 총 3번을 제출했고, 마지막 한번만 맞았다. 처음에 푼 방법은, ArrayList에 char를 집어넣고 커서를 ArrayList의 size로 시작해서 LDBP를 구현했다. 풀면서 무조건 시간초과가 뜰거라고 생각했고, 9%에서 시간초과가 떴다. 그래서, 위의 방법과 커서는 똑같이 가져가고 ArrayList대신 StringBuffer로 문자열을 제거, 추가했다. 몰랐는데, StringBuffer에도 index에 값을 넣는 input 이라는 메소드가 존..
-
BOJ) 성곽알고리즘/백준 2020. 7. 6. 18:18
성곽 2234번: 성곽 문제 대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로� www.acmicpc.net 풀이 생각보다 코드가 길어진 문제다. 각 방에 대해 상하좌우에 벽이 있는지 없는지를 int형 숫자로 주어진다. 이 숫자는 각각 벽이 있다는 의미를 가진 2진수 숫자를 모두 더한 값이다. 벽의 방향 숫자 서 1 북 2 동 4 남 8 위의 벽 정보에 따라서 map의 숫자가 정해진다. 만약 서쪽과 북쪽에 벽이 있다면, 해당 방의 숫자는 3으로 주어지고, 동쪽과 남쪽은 12가 주어지는 식이었다. 그래서, 거추장스럽지만 0~15까지 움직일 수 있는 방향을 미리 저장했다. (..
-
BOJ) 숫자판 점프알고리즘/백준 2020. 7. 6. 18:01
숫자판 점프 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 풀이 5x5 크기의 숫자판에서 숫자 6개를 골라, 만들 수 있는 숫자의 갯수를 구하는 문제다. 또한, 000001 or 000000과 같은 숫자가 허용되고 이동할 때는 먼저 거쳐간 칸을 다시 거쳐가도 된다는 조건이 있다. 따라서, int형보다는 String으로 문제를 푸는 것이 적합하다고 생각했고, visit이 필요없는 문제였다. 그래서 처음에는 dfs안에서 좌표 for문을 돌면서 각 좌표 상하좌우에 있는 ..