변수초기화를생활화하자! 변수초기화를생활화하자! 변수초기화를생활화하자! ㅠㅠㅠㅠ https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 수의 범위가 크지 않아서 DP배열을 선언하기 그리 어렵지 않다. DP배열을 선언해두고 dfs나 bfs 등의 방법으로 가능한 가짓수 여섯가지 경우에 대해 탐색을 해주면 되는데, 탐색 중간에 SCV의 체력이 음수로 내려가는경우 음수 인덱스에 접근하게 되면서 세그폴트가 발생할 수 있으므로, k = max(k,0) 등의 구문을 통해서 ..

숫자범위 자비좀.... https://www.acmicpc.net/problem/2870 2870번: 수학숙제 종이에서 찾은 숫자의 개수를 M이라고 하면, 출력은 M줄로 이루어져야 한다. 각 줄에는 종이에서 찾은 숫자를 하나씩 출력해야 한다. 이때, 비내림차순으로 출력해야 한다. 비내림차순은 내림차 www.acmicpc.net 일단 문제 지문에서 유추해내야 하는 조건으로써 나오는 숫자의 길이가 매우 길어져서 int 및 long long 으로 저장할 수 없는 경우가 있다. 따라서 숫자를 다룰생각을하지를 말고 문자열로 다뤄줘야 하는 문제. 문자열을 가지고 놀기 위해서 몇몇가지 함수를 짜줬다. 1. bool isalpha(char c) 들어온 글자 한글자가 영문자인지 체크하는 함수. bool isalpha(c..

소수이면서 팰린드롬인 수를 구하는 문제. 문제에서 요구하는대로 소수인 수들을 미리 구해놓고, 이들 중에서 팰린드롬인 수를 찾으면 된다. https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 소수의 판정은 에라스토테네스의 체 방법을 활용했다. sleve[0] = 1; sleve[1] = 1; for(int i=2; i

https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net R이랑 B 두가지 색을 가진 공을 적절하게 이동시켜서 같은색끼리 모으는 문제이다. 처음 보고 들었던 생각은 R에 0 B에 1 이런느낌으로 숫자할당을 해서 swap 정렬횟수를 세는 inversion counting 유형인줄 알았다. 하지만 인접한 두 원소간의 교환이 아니라서 해당 가설(?) 은 부정됨. 두번째로 생각했던 것은 에서처럼 R이 뭉쳐져 있는 쪽으로 남은 R을 ..

https://www.acmicpc.net/problem/1945 1945번: 직사각형 첫째 줄에 직사각형의 개수 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 직사각형의 왼쪽 아래 꼭짓점의 좌표 xbl, ybl과 오른쪽 위 꼭짓점의 좌표 xtr, ytr이 순서대로 빈칸 하나를 사이 www.acmicpc.net 교내 백준랜덤디펜스 8번. "원점을 지나는 직선" 이 힌트. 어떠한 점(x,y)과 (0,0) 사이 선을 그으면 그 선의 기울기는 y/x 임을 이용한다. 원점에서 그은 어떠한 직선이 직사각형을 지나려면 그 직선의 기울기가 직사각형의 왼쪽 위 꼭짓점에서 그은 선과 직사각형의 오른쪽 아래 꼭짓점에서 그은 선의 기울기 사이에 존재해야한다. 즉, 원점에서 그은 직선을 y=kx라고 ..

https://www.acmicpc.net/problem/16238 16238번: 독수리 첫째 날 1번 칸의 왼쪽에서 날기 시작해 2번 칸의 양을 먹는다. 독수리가 먹은 양의 수는 10마리이다. 2번 칸에 있는 양을 먹었기 때문에, 1번, 2번 칸의 양의 수는 0이 된다. 첫째 날의 밤에 양의 수 www.acmicpc.net 왼쪽 / 오른쪽에서 접근한다는 함정에 안 속아넘어가도록 조심해야하는 문제. 얼핏보면 순서에 굉장한 제약을 받을 거 같지만, 실제로 원하는 값들을 꺼내고자 할때 꺼내고자 하는 값들이 미리 결정된다면 그 값을 꺼내기 위한 최적의 방법은 유일해진다. 값 두개를 순서대로 꺼낼 때 왼쪽에서 접근한다면 더 왼쪽에 있는 값을 먼저 꺼내야 함은 자명하고, 오른쪽에서 접근한다면 더 오른쪽에 있는 값..

추천받아서 풀어본 그리디 문제. https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 처음에는 lis인가 생각했었는데 일단 이건 아니었다. 만약 swap 연산 후에 break 했다면 lis였을지도? 어떠한 숫자가 뒤로 가는 연산은 j 루프 한번으로 충분하기때문에 교환한 원소의 갯수를 기준으로 생각하면 정답에 도달하기가 힘들다. 어떠한 숫자 K에 대해서 swap을 진행한다고 할때, 지문에 나온 코드를 통해서 정렬하면 K는 j에 ..

https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 연속된 고정 길이의 회전초밥들을 골랐을때 + 고정된 한개의 메뉴가 있을때, 초밥의 종류를 최대한 다양하게 가져가도록 하는 문제 15961번은 범위가 매우 크기 때문에 브루트포싱으로 해결할 수 없고, 회전초밥의 길이가 고정적이라는 점에서 착안해서 슬라이딩 윈도우 알고리즘을 적용해서 문제를 해결했다. 초밥의 종류를 관리하는데에는 다양한 방법이 있을 수 있는데, ..

https://www.acmicpc.net/problem/5520 5520번: The Clocks Read nine numbers from the standard input. These numbers give the start positions of the dials. 0=12 o'clock, 1=3 o'clock, 2=6 o'clock, 3=9 o'clock. The example in figure 1 gives the following input data file: www.acmicpc.net 스터디 하면서 풀어본 문제. 일단 제일 처음 든 생각은, 시계를 돌릴때 4번 돌리면 아무 의미가 없어진다는것 시계를 돌릴수 있는 9가지 방법이 주어지는데, 이 9가지 방법 각각을 4n+m번 돌린 경우는 m번 돌..

깔끔하게 풀어내서 마음에 드는 문제 https://www.acmicpc.net/problem/2992 2992번: 크면서 작은 수 정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다. 수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 www.acmicpc.net 정수X의 자릿수를 쪼개서 어찌저찌 만들어도 되겠다만, 문자열 S에 대해서 '0' ~ '9' 사이의 대소관계는 0~9 사이의 대소관계와 똑같이 계산할 수 있고, 문자열의 길이가 서로 다 같아서 문자열의 길이가 달라지는 경우도 고려 안해줘도 되기때문에 X를 정수로 입력받는것이 아니라 문자열 S로 받았고, 문자열 S는 요컨데 char형의 배열이라고 ..