https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 문제 풀이 문제가 어렵지 않아 금방 구현을 해냈고, 아래는 내가 처음 작성한 코드이다. import sys input = sys.stdin.readline n = int(input()) cards = list(map(int,input().split())) m = int(input()) checks = list(map(int,input().split())) for..
https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제 풀이 문제가 길어서 처음에 뭐지 싶었는데 포켓몬 얘기는 중요한 부분이 아니기 때문에 예제 입출력 조건만 잘 읽어보면 이해할 수 있는 문제였다. n개의 포켓몬 이름이 있을 때 이에 대한 m개의 질문과 일치하는 값을 출력하면 되는 문제였고, 바로 코드 작성을 시작했다. 금방 풀 수 있을 줄 알았는데 계속 시간초과가 나서 답답했다. 시간 초과가 난 코드는 다음과 같다...
백준 10815 - 파이썬
https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 풀이 이번 문제는 서로 비교하여 카드가 존재하는지만 확인하면 되는 문제이기 때문에 금방 구현 과정으로 옮겼다. 다만 어떤 알고리즘을 활용하여 탐색을 할까 하다가 일단은 이중반복문을 사용하여 탐색을 하였다. import sys input = sys.stdin.readline n = int(input()) myCard = list(map(int,input().spl..
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 문제 풀이 이번 문제는 설명을 이해하는데 좀 애먹었다. 좌표를 압축한다고는 하는데 입출력 예제를 봐도 이해가 안 돼서 해당 문제를 설명해 둔 글들을 보며 이해를 했다. 여기서 좌표를 압축한다는 내용 때문에 문제를 한번에 이해하기 어려워졌다고 생각하는데 이를 정리하면 다음과 같다. 좌표의 압축 = 해당 값보다 작은 값들의 개수로 대체 이 점만 알게..
https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 문제 풀이 이번 문제는 등차수열의 합을 이용해서 풀면 되겠다는 생각이 들었다. 하지만 1부터 20까지 모두 더했을 때 나오는 수는 210이므로 예제 입력 값과 약간 차이가 있었다. 심지어 1부터 20까지는 총 20개인데 예제 출력은 19개가 나왔기 때문에 처음에 더 당황했다. 하지만 문제를 잘 읽어보면 서로 다른 N개의 합이라고만 명시되어 있지 꼭 수가 일정하게 증가해야 한다는 조건은 없다. 그래서 이번에는 반대로 200에서 1씩 증가시키면서 빼보기로 했다. 200 - 1 = 199 199 - 2 = 197 198..
https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제 풀이 이번 문제는 완전 탐색이면서도 그리디 알고리즘과도 연관될 수 있는 문제이다. 주어진 N kg 설탕을 5kg과 3kg 봉지를 활용하여 가장 적은 봉지 수를 찾는 것이다. 그렇기에 문제를 보자마자 가장 큰 수인 5로 나눠지는 수를 찾는 게 이 문제의 핵심이라고 생각되었다. 처음에 떠올린 알고리즘은 5를 반복문이 종료될 때까지 계속 빼주면서 3으로 나눠지는 수를 찾는 것이었다. T = int(input..
https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 문제 풀이 이번 문제는 이해하는데 시간이 걸렸다. 2번째 시리즈는 1666, 3번째는 2666 이렇게 666 앞에 있는 숫자가 하나씩 증가한다는 것은 이해했으나 입력이 500일때 왜 166699가 나오는지 이해를 못했다. 잘 생각해 보니 666이 포함된 숫자의 500번째가 166699라는 것을 알 수 있었고, 구현이 어려워 보이지 않아 바로 코드를 작성해 봤다. n = int(input()) c..
https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 풀이 이번 문제는 생각을 코드로 유도하기가 어려운 문제였다. 처음에는 현재 인덱스의 값과 다음 인덱스의 값이 같다면 다르게 바꿔주고 카운트를 해주면 되겠구나 싶어 간단하게 생각했었다. 하지만 이럴 경우 올바르게 색칠하긴 하지만 최솟값을 구할 수 없었다. 그래서 각 줄마다 바꿔야 하는 최솟값을 찾아낸 후 더하면 되겠다 싶어 아래와 같은 알고리즘을 생각해 냈다. 1. 흰색과 검정으로 시작..