J_3s

[ BOJ ] 16234번 : 인구 이동 문제 : https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net [ 문제 ] N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동..

[ BOJ ] 7576번 : 토마토 문제 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net [ 문제 ] 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토..

[ BOJ ] 21922번 : 학부 연구생 민상 문제 : https://www.acmicpc.net/problem/21922 21922번: 학부 연구생 민상 첫 번째 줄에는 연구실의 크기가 세로 $N(1 \le N \le 2,000)$, 가로 $M(1 \le M \le 2,000)$ 순으로 주어진다. 두 번째 줄부터 $N + 1$ 줄까지 연구실 내부 구조 정보를 알려주는 값 $M$개가 주어진다. $1,2,3,4$ www.acmicpc.net [ 문제 ] 학부 연구생으로 새로 연구실에 들어온 민상이는 사용할 자리를 정하려고 한다. 연구실은 격자 모양으로 되어있고 에어컨에서 바람이 상,하,좌,우 4방향으로 분다. 물론 에어컨이 위치한 곳에도 바람이 분다. 민상이는 더위를 많이 타서 에어컨 바람이 지나가는 곳..

[ BOJ ] 12904번 : A와 B 문제 : https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net [ 문제 ] 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때,..

[ 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만으로 시간초과가 뜰 수 있다. 따라서 오른쪽 식처럼 누적합을..