문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 가장 효율적으로 보석을 훔치고 보석 가격의 최댓값을 출력하는 문제 가방 크기에 맞게 보석을 담는다. 담을 수 있는 보석이 있다면 가장 큰 값을 가진 보석을 담는다. 해결해야 하는 부분은 위와 같으며, 이를 우선순위큐(heap)를 이용하여 문제를 해결해 보았다. 주의해야 할 점 가방의 크기는 오름차순으로 정렬해야 한다. 왜냐하면..
문제 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 풀이 정수 A를 B로 주어진 연산을 이용해 만드는 문제 주어진 연산은 다음과 같다. 2를 곱한다 1을 수의 가장 오른쪽에 추가한다. 일단 B에서 A로 바꾸는 풀이로 문제를 해결했다. 첫 번째로 끝이 1이라면 제거해 본다. 두 번째로는 짝수인 경우 2로 나누어 본다. A로 바꾸는 데 성공한 경우 횟수를 출력한다. BFS로 풀 필요는 없고 다른 방법으로 풀 수 있는 문제이다. 제출 코드 # 2023/03/08 bfs # https://www.acmicpc.net/problem/16953 from collections i..
문제 https://www.acmicpc.net/problem/5086 5086번: 배수와 약수 각 테스트 케이스마다 첫 번째 숫자가 두 번째 숫자의 약수라면 factor를, 배수라면 multiple을, 둘 다 아니라면 neither를 출력한다. www.acmicpc.net 풀이 주어진 조건에 따라 그에 맞는 정답을 출력하는 문제 b가 a에 나누어진다면 a가 b의 약수이다. a가 b에 나누어 진다면 a가 b의 배수이다. 위의 두 경우가 아닌 경우 이외의 경우이다. 위의 조건에 맞게 if 문을 작성하면 된다. 제출 코드 # 2023/03/08 구현 # https://www.acmicpc.net/problem/5086 while True: a, b = map(int,input().split()) if a +..
문제 https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 풀이 숫자판이 주어졌을 때 서로 다른 여섯 자리의 수들의 개수를 구하는 문제 각각의 위치에서 DFS를 이용해 탐색을 한다. 현재 위치에서 네 방향으로 움직여 보고 현재 숫자에 더하고, depth + 1을 한 후 이동한다. depth가 5인 경우는 처음 숫자를 포함해 총 여섯 자리이므로 res에 추가한다. res는 set()으로 선언되었으므로 중복된 ..
문제 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 풀이 0부터 시작해서 1에 도착하면 되는 문제 가는 길에 'A'부터 'F'까지 있는 문이 있고, 그에 대응하는 'a'부터 'f'의 열쇠로 문을 열 수 있다. 문이 있지만 열쇠는 없을 수 있으므로 주의해야 한다. (그 반대인 경우도 있다.) 첫 번째 방법으로 열쇠를 먹으면 방문 기록을 초기화하고, 다시 찾아가는 방법을 시도했었다. 그러나, 다른 최적의 방법이 있는..
1. 홈페이지 접속 https://www.python.org/ 2. Downloads를 눌러 'Download Python 3.11.2' 클릭(2023/03/07 기준) 3. 본인의 환경에 맞게 선택 4. 'Add python.exe ot PATH'를 체크 후 Install Now 클릭 'Add python.exe to PATH'는 환경변수에 파이썬 경로를 자동으로 추가하므로 체크해 두면 편하다. 5. 설치 확인(cmd) 작업 표시줄을 확인하면 최근에 추가한 앱에 Python 파일들이 있고, cmd에 python을 입력하면 Python [버전]이 나온다면 정상적으로 설치가 완료된 것이다.. 실행 후 '>>>'으로 표시되어 있는데 이 칸에 파이썬 문법을 사용해 출력해 볼 수 있다.
대회 링크 https://codeforces.com/contest/1800 A. Is It a Cat? https://codeforces.com/contest/1800/problem/A 문제 풀이 주어진 조건에 맞춰 "MEOW"란 단어가 될 수 있는지 확인하는 문제 주어진 문자열 안에 "MEOW"를 제외한 단어가 들어가면 불가능 "MEOW"의 순서가 바뀐 경우 불가능 문자열 전체를 확인해서 가능한지를 확인해 본다. 입력은 upper() 또는 lower()로 받아야 한다. 해당 문자열이 "MEOW" 안에 없는 경우 불가능한 것이므로 flag = False이고, 종료한다. 해당 문자열의 현재 위치에서 좌우를 확인해서 "MEOW"의 순서가 다를 경우 불가능한 것이므로 flag = False이고, 종료한다. 현..
문제 https://www.acmicpc.net/problem/27649 27649번: 토크나이저 첫째 줄에 셸 명령문 $S$가 주어집니다. 명령문은 구분자와 알파벳 대소문자, 숫자 및 $, ?, +, _로 이루어져 있습니다. & 또는 |가 홀수 번 연속으로 주어지지 않습니다. $(|S|\le1\,000\,000)$ www.acmicpc.net 풀이 문자열 처리 방법을 시험받는 문제 구분자에 따라 처리하는 방법을 다르게 하면 된다. 구분자에 해당하는 문자( ' ', ' ( ', ' ) ', '&&', '||' )가 나온 경우 이전에 저장해 두었던 문자열을 res 배열에 추가한다. '&&' 또는 '||'같은 경우 이동 값을 하나 더 준다.(flag, i + 2) 마지막에 남은 단어도 추가한..