728x90 백준41 [BOJ/Python] 14503. 로봇 청소기 📌 문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 📌 문제 접근 방법 바보같이 문제 파악을 잘 못해서 어어어어엄청 헤맸다😣 문제를 찬찬히 살펴보자면, 1) 현재 위치를 청소한다. 2) 현재 위치에서 왼쪽 방향부터 차례로 인접한 칸을 탐색한다. 2-1) 청소할 공간이 있다면, 해당 방향(청소할 공간의 방향)으로 회전하여 전진한다. 2-2) 네 방향 모두 청소할 수 없다면, 바라보는 방향(마지막으로 탐색한 방향)을 유지한 채로 후진한다. .. 2021. 10. 13. [BOJ/Python] 5556. 타일 📌 문제 https://www.acmicpc.net/problem/5556 5556번: 타일 상근이는 타일로 작품을 만드는 예술가이다. 크기가 N × N인 작품을 만들기 위해서 상근이는 1 × 1 타일을 사용한다. 색상은 빨강, 파랑, 노랑 중 하나이다. 작품은 가장 바깥쪽에 빨간색을 붙이 www.acmicpc.net 📌 문제 접근 방법 처음엔 타일의 인덱스를 받아서 타일이 바깥쪽에서 얼마나 안으로 들어와있는지를 num을 통해서 구했다. → 시간초과 시간초과가 나고 N의 범위를 보니, 타일의 인덱스를 받자마자 거기서 계산해서 바로 나와야 하는 것 같았다. 우선, 타일의 인덱스를 타일의 중심을 기준으로 왼쪽 위부분만 고려하도록 인덱스를 변형해줬다. 왼쪽 위 부분만 본다면, 한 행에 i개의 색깔을 쓸 수 있.. 2021. 10. 9. [BOJ/Python] 2579. 계단 오르기 📌 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 📌 문제 접근 방법 첫 번째 칸을 밟는 경우, 최대값은 첫 번째 칸의 점수 두 번째 칸을 밟는 경우, 최대값은 첫 번째 칸 + 두 번째 칸의 점수 세 번째 칸을 밟는 경우, 첫 번째 칸 + (2칸 이동) 세 번째 칸 두 번째 칸 + (1칸 이동) 세 번째 칸 i번째 칸을 밟는 경우, i-3번째 칸 + (2칸 이동) i-1번째 칸 + (1칸 이동) i번째 칸 i-2번째 칸 + (1칸 이동) i번째 칸 .. 2021. 10. 8. [BOJ/Python] 1208. 부분수열의 합2 📌 문제 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 📌 문제 접근 방법 시간 초과를 피하기 위해 리스트를 2개로 나누어 준다. (N의 최대값은 40으로, 나누지 않고 부분집합을 구할 경우 2^40번의 연산이 필요하다. 둘로 나눌 경우, 2^20 + 2^20번의 연산으로 줄일 수 있다.) left, right로 나눈 두 개의 부분집합에 대해서 나올 수 있는 합의 경우의 수를 구한다. 투 포인터를 활용하.. 2021. 10. 8. 이전 1 2 3 4 5 6 7 8 ··· 11 다음 728x90