🪨 🪨 🪨

https://www.acmicpc.net/problem/27210 27210번: 신을 모시는 사당 칠할 수 있는 돌상의 개수에 제한은 없으며, 반드시 연속한(인접한) 돌상들만 칠할 수 있음(띄엄띄엄 칠할 수 없음)에 유의하라. www.acmicpc.net 원티드 쇼미더코드 3회차 문제 중 풀이에는 가장 짧은 시간이 들었지만, 코드가 가장 자신 없는 문제이다. 우선, 돌상이 왼쪽을 보고 있을 때는 누적값에 1을 더해주고, 돌상이 오른쪽을 보고 있을 때는 1을 빼주는 방식으로 누적값(curr 변수)을 계산했다. 예시를 하나 만들어보자면, 누적값을 아래와 같이 계산할 수 있다. 인덱스 : 0 1 2 3 4 5 6 7 8 9 10 방 향 : 왼 오 왼 왼 오 오 오 오 오 왼 누적값 : 0 1 0 1 2 1 ..

https://www.acmicpc.net/problem/27211 27211번: 도넛 행성 준겸이는 $N \times M$칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 www.acmicpc.net 문제의 그림이 어마무시했는데... 그냥 그래프 탐색 문제였다. 4963번 섬의 개수, 혹은 2667번 단지번호붙이기와 유사한 문제이다. 유일하게 추가된 조건은 0번 행과 (N-1) 번 행이 연결되어 있고, 0번 열과 (M-1) 번 열이 연결되어 있다는 점이다. 이 조건을 고려해서 인접한 칸을 탐색할 때 0

https://www.acmicpc.net/problem/27212 27212번: 미팅 오늘은 A대학의 학생 $N$명과 B대학의 학생 $M$명이 만나는 날이다. 이들이 만나는 장소에는 크고 길이가 긴 식탁이 하나 있어서, 한쪽에는 A대학 학생이, 다른 한쪽에는 B대학 학생이 앉을 예정이 www.acmicpc.net 악수 얘기만 들었을 때는 전깃줄 문제가 떠올랐는데 갑자기 만족도를 구하라고 한다. DP로 접근해서 해결했다. dp[a][b]는 A대학 a번 학생이 B대학에서 b번 이하의 학생과 악수를 할 수 있을 때 얻을 수 있는 총만족도의 최댓값으로 정했다. 말이 이상한데, 예를 들어 문제의 예제를 살짝 변형해서 아래와 같은 조건이 있다고 치자. W = | 10 1 | | 1 10 | A = [1, 2] B..

https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 두 원의 교점의 수를 구하는 문제이다. 중학교였나 고등학교였나 먼 과거에 배웠던 내용인데, 경우만 잘 따져주면 된다. 먼저, 두 점 사이의 거리 공식을 이용해 원의 중심 사이의 거리인 d를 구해준다. #1 원의 중심이 동일하고 반지름도 동일하다면 두 원이 서로 같고, 접점의 개수가 무한대이다. -1을 출력한다. #2 두 원의 반지름의 합(r1 + r2)이 d와 같거나 반지름의 차(abs(r1 - r2))가 d와 같다면 각각 외접, 내접하는 경우이다...

https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net set 자료형을 이용해서 데이터를 다루는 문제이다. 데이터의 수가 최대 10 ** 6이어서 빠른 입출력을 사용하지 않거나 list를 사용하면 시간 초과가 난다. at_company라는 set 자료형을 생성해 줬다. 한 줄씩 input을 받으면서 만약 출근을 했다면 at_company에 add 해주고, 퇴근을 했다면 at_company에서 remove 해준다...

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net dp와 수학 두 가지 방법으로 풀었다. - dp 풀이 dp 배열을 선언해 여기에 답을 저장해가며 풀 수 있다. dp[n]은 n kg의 설탕을 옮기는 데 필요한 최소한의 봉지의 수를 의미한다. 계산이 귀찮지 않도록 dp[3]과 dp[5]는 1로 초기화해 준다. dp의 길이가 (N+1)이 아니라 max(6, N+1)인 이유는 초기화 과정에서 index 에러가 발생하지 않도록 하기 위함이다. 6 kg부터 N kg..

처음 백준을 접할 때 입력, 출력 관련해서 고생을 좀 했었어서 기록을 남겨본다. 1. 입력이 한 줄에 하나씩 들어옴 input() 함수를 통해 입력을 받을 수 있다. 단, string으로 입력값이 받아지므로 숫자로 받고 싶다면 형 변환이 필요하다. N = input() # N = "3" N = int(input()) # N = 3 입력값이 여러 줄인 경우에도 마찬가지이다. N = int(input()) # N = 5 for _ in range(N): print(input()) # 이후의 입력을 한 줄씩 프린트 파이참에서 input() 함수로 입력값을 받을 때, 백준 예제 입력을 복붙해서 엔터를 치면 마지막 줄 입력값이 반영이 안 되는 경우가 자주 있다. 이런 경우에는 그냥 엔터만 한 번 더 쳐주면 정상적..

https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 가장 잘 알려진 풀이는 스택을 두 개 사용하는 것이다. 커서를 기준으로 왼쪽에 위치한 스택과 오른쪽에 위치한 스택 두 개를 만든다. 오른쪽 스택은 방향을 뒤집어두었다. pop 하면 왼쪽에 있는 원소가 나오고, append도 왼쪽에 된다. 처음에는 문장의 맨 뒤에 커서가 위치하므로 왼쪽 스택에 문자를 순서대로 넣어두면 된다. 커서는 항상 left 리스트 오른쪽에 있다. 만약 "P"라는 명령어가 들어오..

https://www.acmicpc.net/problem/2941 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 영어 알파벳은 알파벳 하나의 길이가 1이다. 따라서 "abcde"에서 알파벳의 개수는 문자열의 길이와 동일한 5이다. 하지만 크로아티아 알파벳은 길이가 1~3이므로 이를 고려해서 계산해주어야 한다. 예제 1번인 "ljes=njak"의 경우에는 lj, e, s=, nj, a, k 6개의 알파벳으로 구성되어 있고, 예제 2번인 "ddz=z="의 경우에는 d, dz..

https://www.acmicpc.net/problem/1943 1943번: 동전 분배 세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1 ≤ N ≤ 100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원 www.acmicpc.net dp로 해결할 수 있는 냅색 문제이다. Python3을 이용해 AC를 받은 사람이 단 4명으로, 그냥 Pypy로 제출하는 것이 정신 건강에 이롭다. 난 그마저도 시간 초과, 오답 파티를 했다. 일단 input을 받으면서 선생님한테 받은 전체 금액을 계산한다. 만약 전체 금액이 홀수라면 윤화와 준희가 모두 만족할 수는 없으므로 굳이 계산을 할 필요 없이 0을 출력하고 넘어간다. 반띵이..