취업 준비 및 일상

https://www.acmicpc.net/problem/25201 25201번: 보드 뒤집기 게임 첫 번째 줄에는 현재 격자판 상태에서의 빨간색으로 칠해진 칸의 좌표의 개수 $N$, 곰곰이가 원하는 격자판 상태에서의 빨간색으로 칠해진 칸의 좌표의 개수 $M$ 이 공백을 사이에 두고 주어진다 www.acmicpc.net 풀이 인터넷 서핑하다가 우연히 1줄 풀이를 보고, '그냥 구현만 해서 날로 먹을까?' 했는데 그러기엔 양심이 찔려서 정리했습니다. 곰곰컵 공식 풀이가 있습니다만, bijection 부분부터 모르겠어서 이와 유사한 문제인 Codeforces Global Round 2 C번 문제의 Editorial을 보고 이해했습니다. 다음 명제는 참입니다: '곰곰이가 뒤집기 마법을 사용하여 현재 격자판에서..

https://www.acmicpc.net/problem/14622 14622번: 소수 게임 인하대학교에 다니는 대웅이는 정수론을 정말 좋아한다. 정수론을 광적으로 좋아하는 대웅이는 어느 순간부터 소수를 외우기 시작했고 어떤 수를 말하면 그 수가 소수인지 아닌지 판별할 수 있 www.acmicpc.net 풀이 에라토스테네스를 이용하여 500만 미만의 소수를 저장합니다. 또한, 특정 소수를 방문했는지 기록할 boolean 배열도 하나 선언해줍시다. 대웅이와 규성이가 번갈아가면서, 1) 소수가 아닌 수를 불렀는지, 2) 이미 부른 소수를 불렀는지, 3) 한 번도 안 부른 소수를 불렀는지를 체크하여 문제 조건대로 처리해줍니다. N은 최대 10만이기에, 3번째로 큰 소수를 배열같은 곳에 저장하면 당연히 시간초과..

https://www.acmicpc.net/problem/15792 15792번: A/B - 2 첫째 줄에 A와 B가 주어진다. (0 < A, B ≤ 10,000) www.acmicpc.net 문제 두 정수 A와 B를 입력받은 다음, A/B를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 A와 B가 주어진다. (0 < A, B ≤ 10,000) 출력 첫째 줄에 A/B를 출력한다. 서브태스크 번호배점제한 1 1 절대/상대 오차는 10-1 까지 허용한다. 2 2 절대/상대 오차는 10-2 까지 허용한다. 3 6 절대/상대 오차는 10-6 까지 허용한다. 4 9 절대/상대 오차는 10-9 까지 허용한다. 5 20 절대/상대 오차는 10-20 까지 허용한다. 6 50 절대/상대 오차는 10-50 까지 허용한다..

https://www.acmicpc.net/problem/9082 9082번: 지뢰찾기 지뢰찾기 게임은 2×N 배열에 숨겨져 있는 지뢰를 찾는 게임이다. 지뢰 주위에 쓰여 있는 숫자들로 지뢰를 찾을 수 있는데, 한 블록에 쓰여진 숫자는 그 블록 주위에 지뢰가 몇 개 있는지를 나타 www.acmicpc.net 문제 지뢰찾기 게임은 2×N 배열에 숨겨져 있는 지뢰를 찾는 게임이다. 지뢰 주위에 쓰여 있는 숫자들로 지뢰를 찾을 수 있는데, 한 블록에 쓰여진 숫자는 그 블록 주위에 지뢰가 몇 개 있는지를 나타낸다. 지뢰가 확실히 있는 위치를 *, 숨겨진 블록을 #으로 표시한다. 첫째 줄에는 숫자만 나타나고 둘째 줄에는 *와 #만 나타나는데, 지뢰는 둘째 줄에만 있다. 12110 ##*## 위의 그림 2×5 배열..

https://www.acmicpc.net/problem/3343 3343번: 장미 첫째 줄에 N, A, B, C, D가 주어진다. N은 1015를 넘지 않으며, A, B, C, D는 105를 넘지 않는다. www.acmicpc.net 문제 상근이는 발렌타인 데이를 기념해 여자친구에게 노란 장미 N개를 선물하려고 한다. 상근이네 집 근처에 꽃집의 수는 두 개이다. 두 꽃 집은 발렌타인 대이를 대비해 많은 꽃을 준비했기 때문에, 꽃이 부족한 일은 없다. 하지만, 두 곳 모두 장미를 다발로 묶어서 판다. 첫 번째 꽃집은 장미 A개를 B원에 팔고, 두 번째 꽃집은 C개를 D원에 판다. A, B, C, D는 모두 양의 정수이다. 만약, 장미 N개를 보다 많이 구매하는 것이 정확하게 N개를 구매하는 것 보다 가격..

https://www.acmicpc.net/problem/1790 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net 문제 1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다. 1234567891011121314151617181920212223... 이렇게 만들어진 새로운 수에서, 앞에서 k번째 자리 숫자가 어떤 숫자인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. 출력 ..

https://www.acmicpc.net/problem/24553 24553번: 팰린드롬 게임 첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 1\,000$) 둘째 줄부터 $T$개의 줄에 걸쳐, 돌 무더기에 쌓여 있는 돌의 개수 $N$이 주어진다. ($1 \le N \le 10^{18}$) www.acmicpc.net 풀이 20~30정도까지 누가 이기는지 적다보면 '어? 10의 배수면 상윤이가 지고 아니면 상윤이가 이기겠네?'하는 감이 올 것이다. '10의 배수이면 상윤이가 지고, 아니면 상윤이가 이긴다'를 1~10*N에 대해서 증명하면 된다. 수학적 귀납법으로 증명하도록 한다. 1) N==1일 때: 성립한다 2) 임의의 자연수 M에 대하여 1~10*M에서 10의 배수일때만..

문제 주헌이는 매운맛을 좋아한다. 정확히는, 매운맛을 먹음으로써 느낄 수 있는 고통에서 희열을 느끼는 진정한 '즐기는 자'다. '스코빌 지수'란 고추류가 가진 매운맛의 원인인 캡사이신의 농도를 수치화 한 단위이다. 주헌이가 느끼는 매운 정도는 굉장히 독특한데, 먹고 있는 메뉴의 절대 수치가 아닌 음식과의 상대수치에 기반한다. 예를 들어 [5, 2, 8]의 스코빌 지수를 가진 음식을 먹을 때 주헌이가 느끼는 매운 정도는 가장 높은 수치인 8과 가장 낮은 수치인 2의 차이인 6만큼의 매운맛을 느낀다. 이처럼 메뉴들의 스코빌 지수가 있을 때 그 최댓값과 최솟값의 차이를 "주헌고통지수"라고 정의한다. 그림1. 고추처럼 보이지만 문제와는 무관합니다. 최근 주헌이에게 좋아하는 매운맛 전문점이 생겼다. 메뉴가 아주 ..

문제 151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되고 이 두 수가 다르기 때문에 팰린드롬이 아니다. 두 정수 a, b가 주어졌을 때, a이상 b이하인 소수인 팰린드롬을 모두 구하는 프로그램을 작성하시오. 입력 입력은 첫째 줄에 공백으로 구분된 두 자연수 a, b가 주어진다. 단 5 ≤ a < b ≤ 100,000,000 이다. 출력 첫째 줄부터 차례로 증가하는 순서대로 한 줄에 한개씩 소수인 팰린드롬을 출력한다. 마지막 줄에는 -1을 출력한다. 풀이 b까지 소수를 에라토스테네스 체를 이용하여 구한 후, 소수에 대하여 팰린드롬인지 확인한다. 1. 개선..

문제 우석이는 심심할 때마다 그래프를 그린다. 우석이는 매달 새로운 그래프를 그리는데, 이번 달에는 서로소 그래프를 그린다. 서로소 그래프는 1부터 N까지의 번호를 가진 N 개의 정점으로 이루어져 있으며, 서로 다른 두 정점의 번호가 서로소일 때만 두 정점이 간선 하나로 직접 연결되어 있다. 우석이는 간선을 얼마나 많이 그려야할지 궁금해졌다. 정점의 개수 N이 주어질 때, 만들어야 하는 간선의 개수를 알려주자. 입력 첫째 줄에 그래프의 정점 개수 N이 주어진다. 출력 우석이가 그려야하는 간선의 수를 출력한다. 제한 1≤N≤50000 풀이 임의의 자연수 N에 대하여, N보다 작은 수 중 N과 서로소인 수의 개수는 phi(N) (phi: Euler's phi function) 개이다. 주어진 문제를 살펴보면..