J_3s

[ BOJ ] 15558번 : 점프 게임 문제 : https://www.acmicpc.net/problem/15558 15558번: 점프 게임 첫째 줄에 N과 k가 주어진다. (1 ≤ N, k ≤ 100,000) 둘째 줄에는 왼쪽 줄의 정보가 주어진다. i번째 문자가 0인 경우에는 위험한 칸이고, 1인 경우에는 안전한 칸이다. 셋째 줄에는 오른쪽 줄의 정보 www.acmicpc.net [ 문제 ] 상근이는 오른쪽 그림과 같은 지도에서 진행하는 게임을 만들었다. 지도는 총 2개의 줄로 나누어져 있으며, 각 줄은 N개의 칸으로 나누어져 있다. 칸은 위험한 칸과 안전한 칸으로 나누어져 있고, 안전한 칸은 유저가 이동할 수 있는 칸, 위험한 칸은 이동할 수 없는 칸이다. 가장 처음에 유저는 왼쪽 줄의 1번 칸 ..

[ BOJ ] 11899번 : 괄호 끼워넣기 문제 : https://www.acmicpc.net/problem/11899 11899번: 괄호 끼워넣기 첫 번째 줄에 S를 올바른 괄호열으로 만들기 위해 앞과 뒤에 붙여야 할 괄호의 최소 개수를 출력합니다. 불가능한 경우는 주어지지 않습니다. www.acmicpc.net [ 문제 ] 심심한 승현이는 너무 심심한 나머지 올바른 괄호열을 가지고 놀고 있었습니다. (()(()))()() 그러다가 어쩌다 보니 괄호열을 부러뜨렸습니다. (() (( )))() () 크게 낙담한 승현이는 노력해 보았지만, 대부분이 부러져 버려 단 한 부분만 재사용할 수 있다는 것을 깨닫게 되었습니다. )))() 승현이는 이 괄호열을 가지고 놀려고 했으나 올바른 괄호열이 아니기 때문에 행..

[ BOJ ] 1012번 : 유기농 배추 문제 : https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net [ 문제 ] 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고..

[ BOJ ] 14929번 : 귀찮아 (SIB) 문제 : https://www.acmicpc.net/problem/14929 14929번: 귀찮아 (SIB) n과 xi가 주어짇나. n은 10만 이하ㅇ고, xi는 젗ㄹ댓값이 100이하인 정수디이다. www.acmicpc.net [ 문제 ] [ 입력 ] \(n\)과 \(x_i\)가 주어짇나. n은 10만 이하ㅇ고, \(x_i\)는 젗ㄹ댓값이 100이하인 정수디이다. [ 문제 접근 및 풀이 ] $$ x_1x_2 + x_1x_3 + x_2x_3 = x_1(x_2+x_3) + x_2x_3 $$ 왼쪽의 식처럼 각각의 항들을 직접 2중 for문으로 구하게 된다면 \(O(n^2)\)으로 n의 크기가 최대 10만으로 시간초과가 뜰 수 있다. 따라서 오른쪽 식처럼 누적합을..